[LeetCode] 35. Search Insert Position (Javascript)

[LeetCode] 35. Search Insert Position (Javascript)

 

Source

https://leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

 

Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

var searchInsert = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;
  let mid = 0;

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

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

 

How to solve?

1. 값의 범위는 0부터 n까지이다.

2. binary search를 구현한 뒤 마지막에 남겨진 값을 본다.

3. left > right이면서 해당하는 값이 0인 경우, 배열의 중간에 있는 경우, 배열의 최대 인덱스보다 큰 경우 모두 left가 해당 위치에 있기 때문에 while문은 넘어간다면 left를 return해준다.

 

값의 범위에 대한 자세한 설명

https://leetcode.com/problems/search-insert-position/solutions/423166/binary-search-101/?orderBy=hot&languageTags=javascript 

Binary Search 101 - Search Insert Position - LeetCode