풀이
이진 탐색으로 하한(lower bound), 즉 target보다 크거나 같은 첫 번째 값의 인덱스를 찾습니다. 반열린 탐색 구간 [left, right)을 유지하며, 처음에는 모든 유효한 배열 인덱스를 포함합니다. 매 단계에서 left보다 앞에 있는 모든 값은 target보다 작고, right부터 뒤에 있는 모든 값은 target보다 크거나 같다는 불변식을 유지합니다. 중간 값이 target보다 작으면 left를 중간 인덱스 다음으로 옮기고, 그렇지 않으면 right를 중간 인덱스로 옮깁니다. 구간이 줄어들어 left == right가 되면 그 위치가 하한입니다. 모든 값이 더 작다면 결과는 nums.length이며, 빈 배열도 자연스럽게 0을 반환합니다. target과 같은 값이 여러 개 있어도 첫 번째 위치를 찾습니다.
시간 복잡도는 O(log N), 추가 공간 복잡도는 O(1)입니다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}