[leetcode] Search Insert Position

35. 삽입 위치 검색

고유한 정수와 대상 값의 정렬된 배열이 주어질때 대상이 발견되면 인덱스를 반환합니다.
그렇지 않은 경우, 인덱스를 순서대로 삽입한 경우 인덱스를 반환합니다.

런타임 복잡도가 O(log n)인 알고리즘을 작성해야 합니다.

예 1:
입력: nums = [1,3,5,6], target = 5
출력: 2

예 2:
입력: nums = [1,3,5,6], target = 2
출력: 1

예 3:
입력: nums = [1,3,5,6], target = 7
출력: 4

 

 

문제 정리

1. 정렬된 배열이 주어질때, 배열안에 target의 정수가 있다면 target이 몇 번째인지 반환한다.
만약 target 정수가 발견되지 않는다면 배열의 정렬순으로 target이 몇 번째 있는지 인덱스를 반환하는 문제이다.

생각한 방법 (이진탐색 알고리즘)

1. 정렬된 배열에서 target을 찾아내기 위해 가장 효율적인 방법인 이진탐색 알고리즘을 사용한다.

이진탐색 알고리즘이란?
이진탐색은 탐색 범위를 반으로 줄여 나가면서 원하는 값을 찾기때문에, 반복 횟수가 미리 정해져있지 않는다.
이런 경우에는 while문이 더 적합하다. for문은 반복 횟수가 미리 정해진 경우에 주로 사용한다.

예를 들어서 배열의 모든 요소에 대해 작업을 수행하는 경우,
배열의 길이가 미리 알려져 있기 때문에 for 문이 적합하다.
이 문제에서는 탐색 범위가 계속 변화하므로(left, right가 업데이터함) while 문이 적합하다.
while문의 조건은 left <= right로 주어져 있으며 이 조건이 만족되지않는 경우에는 반복이 종료되고
적절한 삽입 위치가 반환된다.

 

작성코드✍️

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

    while (left <= right) {
      let mid = left + Math.floor((right - left) / 2); 

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

  let nums = [1, 2, 3],
    target = 4;

  console.log(searchInsert(nums, target));

 

for문을 사용하지않고 while문을 사용한 이유?

 

이진 탐색 알고리즘을 수행하는 동안 left와 right 값은 각각 업데이트되어 탐색 범위를 좁혀 나가야한다.

left <=  right 조건은 탐색 범위가 아직 유효한지 확인하는 역할을 한다.

left가 right보다 크게 되면 배열안에 target 숫자가 일치하는게 없기때문에 이 경우 while 반복문을 종료한다.

따라서 left <= right는 고정 값이 아닌, left와 right 값의 변화에 따라 계속해서 변경되는 조건으로 만들어야하기때문에 

위 문제에서는 for문보다는 while문이 적합하다.