[Binary Search] Search Insert Position

35. Search Insert Position

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 
 * Runtime	: 46 ms
 * Memory	: 41.91 MB
 */
var searchInsert = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let mid = null;

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

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

  return left;
};

이진 탐색을 사용하였습니다. 단, 중간 인덱스를 구할 때 반올림을 하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

중간 인덱스를 구하는 방법에서만 차이가 있었습니다.

A. mid = left + (right - left) / 2;
B. mid = Math.floor((start + end) / 2);

A 방법은 로직을 이해하는 데 시간이 걸렸습니다.

B 방법은 본 문제와 같이 배열에서 인덱스를 탐색하는 경우에 적절합니다. 만약, 총 숫자에서 특정 숫자를 탐색하는 경우에는 Math.round() 함수를 사용하는 것이 더 적절할 수 있습니다. 필자는 이 2가지 경우 모두 범용적으로 사용하기 위해 Math.round() 함수를 사용하였습니다.