[LeetCode] Search Insert Position - Javascript

Search Insert Position

[주어진 값 찾거나, 순서에 맞게 인덱스 리턴하기]

 

제약 조건 

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4

 

Example

ex1) Input: nums = [1,3,5,6], target = 5
     Output: 2

ex2) Input: nums = [1,3,5,6], target = 2
     Output: 1

ex3) Input: nums = [1,3,5,6], target = 7
     Output: 4

초기 문제 접근 방식

O(log n)으로 반드시 문제를 풀어야 한다고 기재되어 있기에,
이진탐색 방식을 생각했다.

 

이진탐색은 left, mid, right 변수를 생성해
left는 맨 처음 인덱스, mid는 중간 인덱스, right는 맨 마지막 인덱스로 초기화하고
while 문을 left가 right보다 크거나 같을 때까지 순회한다.

 

mid는 left와 right를 더해 2로 나눈 몫 값으로 초기화하고
nums[mid] 값이 target과 같다면 mid의 값을 리턴한다.
target이 더 크다면 left = mid +1으로 업데이트한다.
taget이 더 작으면 right = right -1으로 업데이트한다.
또한 target 값이 배열 인덱스에 없을 수도 있기에 이 땐 left를 리턴한다.

solve 전체 코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length-1;

    while(left <= right){
        let mid = Math.floor((left+right) / 2);

        if(nums[mid] === target){
            return mid
        }else if(nums[mid] < target){
            left = mid+1;
        }else if(nums[mid] > target){
            right = mid-1
        }
    }
    return left
};

 

다른 solve 코드

var searchInsert = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let middle = Math.floor((left + right) / 2);
  while (nums[middle] !== target && left <= right) {
    if (target < nums[middle]) { // target이 작으면 right를 줄인다.
      right = middle - 1;
    } else { // target이 더크면 left를 늘린다. 
      left = middle + 1;
    }
    middle = Math.floor((left + right) / 2);
  }
  // 같아서 while문이 끝난거면 middle, 달라서 마지막에 끝난거면 left의 값을 return한다.
  return nums[middle] === target ? middle : left;
};

해당 코드 또한 비슷한 방식으로 풀이됐다.
nums[middle]이 target보다 크면 right를 하나씩 줄이고
right에는 middle-1으로 업데이트하고
nums[middle]이 더 작다면 left를 middle+1로 업데이트한다.
같아서 while 문이 종료된 거라면 middle을 리턴하고, 달라서 마지막에 끝난 거라면 left의 값을 리턴한다.