참고
문제해설
NOTE
•
입력 값 ⇒ 배열과, taget 정수
•
출력 값 ⇒ target 정수의 idx, 없다면 -1
•
O(log n)의 제한시간을 가진다.
문제 로직고민
NOTE
•
회전 정렬 배열에서 어떻게 바이너리 서치를 사용하는가?
◦
O(log n)의 제한시간을 가지는 만큼 배열에 추가작없이 바로 바이너리 서치 탐색을 진행한다.
◦
하지만 정렬된 배열에서 동작하는 알고리즘에서 회전된 배열의 중앙값은 어떻게 찾는가?
•
바이너리 서치를 활용해서 중앙값을 구한다
◦
left 보다 작다면 right → 중앙값 - 1
◦
right 보다 크다면 left → 중앙값 + 1
◦
이 과정을 진행하면, 가장 작은 숫자에 도달할 수 있다! (시작점)
•
해당 시작점을 기준으로, 바이너리 서치를 진행한다.
◦
시작점을 기준으로 오른쪽 혹은 왼쪽의 범위내에 target이 있으므로, 하나의 범위를 선택해서 바이너리 서치를 진행한다.
작성코드
NOTE
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
int pivot = 0;
while(left < right){
pivot = (left + right) / 2;
if(nums[pivot] > nums[right]) left = pivot + 1;
else right = pivot;
}
pivot = left;
left = 0;
right = nums.length-1;
if(nums[pivot] <= target && target <= nums[right]) left = pivot;
else right = pivot;
while(left <= right){
pivot = (left + right) / 2;
if(target < nums[pivot]) right = pivot - 1;
else if(nums[pivot] == target) return pivot;
else left = pivot + 1;
}
return -1;
}
}
Java
복사
정답코드
NOTE
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
// Find the index of the pivot element (the smallest element)
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[n - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// Binary search over elements on the pivot element's left
int answer = binarySearch(nums, 0, left - 1, target);
if (answer != -1) {
return answer;
}
// Binary search over elements on the pivot element's right
return binarySearch(nums, left, n - 1, target);
}
// Binary search over an inclusive range [left_boundary ~ right_boundary]
private int binarySearch(int[] nums, int leftBoundary, int rightBoundary, int target) {
int left = leftBoundary, right = rightBoundary;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
3MB정도의 메모리 차이가 나는 코드인데, 로직면에서 비슷한걸 보면 참고만하고 넘어가도 될것같다.