[LeetCode] Search Insert Position JavaScript

문제

https://leetcode.com/explore/challenge/card/june-leetcoding-challenge/540/week-2-june-8th-june-14th/3356/

Input: [1,3,5,6], 5
Output: 2

Input: [1,3,5,6], 2
Output: 1

Input: [1,3,5,6], 7
Output: 4

Input: [1,3,5,6], 0
Output: 0

정렬된 배열이 주어지고 주어진 숫자가 어디에 들어가면 좋을지 return 하는 문제이다. 주어진 숫자와 같은 숫자가 있다면 그 숫자의 index를 return 하면 되고 아니라면 들어가도 정렬이 되는 적절한 자리를 찾으면 된다.

나의 코드

나의 풀이는 제일 생각하기 쉬운 O(N)이다. nums 배열이 정렬 되어 있기 때문에 순서대로 target과 비교했고 nums[i]가 크거나 같으면 그 때의 i가 target이 들어갈 자리이기 때문에 return 해주었다.

var searchInsert = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

다른 사람 코드

내 코드는 O(N)이기 때문에 나쁘지 않고 보기도 쉽다. 하지만 시간 복잡도 측면에서 그렇게 좋은 코드는 아닌거 같았다. 다른 분의 코드를 보니 이분탐색을 사용해서 O(logN)의 시간 복잡도를 가졌다.

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;
};