drop-of-water

문제 링크

조건

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums는 오름차순으로 정렬되어 있음
  • -10^4 <= target <= 10^4
  • O(log n) 알고리즘 작성

입력값

  • nums = 오름차 순으로 정렬된 배열
  • target = 찾는 값

출력값

  • 찾는 값이 있으면 해당 값의 index, 없으면 target이 오름차순으로 정렬했을때 들어가야할 index 위치 값

풀이과정

  • Binary search를 사용해 target의 index를 찾음
  • target이 있으면 index return
  • 없는 경우 for 문을 돌면서 target이 들어갈만한 위치를 찾는다

코드

var searchInsert = function (nums, target) {
  let low = 0;
  let high = nums.length - 1;
  let idx = 0;

  // Binary search를 사용해 target의 index를 찾음
  while (low <= high) {
    let mid = Math.floor((high + low) / 2);

    // target이 있으면
    if (nums[mid] == target) {
      // index return
      return mid;
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else if (nums[mid] > target) {
      high = mid - 1;
    }
  }

  //없는 경우 for 문을 돌면서 target이 들어갈만한 위치를 찾는다
  for (let i = 0; i <= nums.length; i++) {
    if (target > nums[i]) {
      idx = i + 1;
    } else break;
  }
  return idx;
};

😊