Search Insert Position

278. First Bad Version

문제

"First Bad Version"에 이어서 이분탐색 응용

배열에서 target 요소를 찾아 인덱스를 반환하거나, 만약 찾지 못한다면 target이 들어갈 자리의 인덱스를 반환한다.

테스트 케이스

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

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

Binary Search

코드는 이전 이분 탐색 코드이다. 모든 배열을 탐색했을 때target을 찾지 못하면 left 인덱스에서 +1 한 값을 리턴한다.

/**
 * @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 {
        right = mid - 1;
      }
    }

    return left + 1;
};

실패

Input: nums = [1,3,5,6], target = 0
Output: 1
Expected: 0

다음과 같은 테스트 케이스가 입력되었을 때, 내가 작성한 코드로는 기댓값인 0이 나올수 없다.
이 방법으로는 기댓값의 최소와 최대의 범위는 1부터 n+1이 되기 때문이다. 이런 오류를 해결하기 위해서는 0과 n을 모두 포함하기 위해서 left와 right의 이동 범위, 리턴문을 수정해야 한다.

target과 nums[mid]의 값이 일치하지 않고 모든 범위를 탐색했을 때, 범위를 -1 혹은 +1 (target 인덱스를 맞추기 위해서) 옮기기 위해 while 조건을 left <= right로 수정했다. 이미 target 인덱스를 맞추었기 때문에 return left를 해주면 되었다.

return left를 하는 이유는

left와 right가 같은 인덱스에 위치했을 때, 범위 안에서
nums[mid] < target조건을 통과해 left의 다음 인덱스를 가리키도록 하기 때문이다.

성공

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 {
        right = mid - 1;
      }
    }

    return left;
};

mid를 계산할 때 오버플로우를 방지하는 방법

// before
let mid = Math.floor((left + right) / 2); // 0, 5 => 2

// after
let mid = left + Math.floor((right - left) / 2);; // 0, 5 => 2

출처

• Binary Search 101 | AminiCK