← 11주차 · 이분 탐색과 결정 알고리즘
보통이분 탐색

삽입 위치 찾기

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어져요. target이 배열에 있으면 그 인덱스를, 없으면 정렬을 유지하며 끼워 넣을 자리의 인덱스를 반환해요.

이건 target 이상인 첫 위치를 찾는 것과 같아요(lower bound). 같은 값이 여러 개면 그 중 가장 앞 위치를 골라요. O(log n)에 풀어요.

예시

예시 1
입력
nums = [1, 3, 5, 6], target = 5
출력
2
설명
5가 인덱스 2에 있어요.
예시 2
입력
nums = [1, 3, 5, 6], target = 2
출력
1
설명
2는 없지만, 넣는다면 1과 3 사이인 인덱스 1이에요.
예시 3
입력
nums = [1, 3, 5, 6], target = 7
출력
4
설명
가장 큰 값보다 커서 맨 뒤인 인덱스 4에 들어가요.

제한 사항

  • 0 ≤ nums.length ≤ 100,000
  • nums는 오름차순으로 정렬돼 있고, 값이 중복될 수 있어요.
  • -10^9 ≤ nums[i], target ≤ 10^9
lo = 0, hi = nums.length로 두고 while (lo < hi)를 돌려요. nums[mid] < target이면 lo = mid + 1, 아니면 hi = mid로 좁혀요. 루프가 끝나면 lo가 바로 답이에요.
javascript
function searchInsert(nums, target) {
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}
이전 문제이진 탐색
다음 문제회전된 정렬 배열에서 검색
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.