beepbeep
LeetCode 33번 - Search in Rotated Sorted Array 본문
문제
배열이 하나 주어집니다.
주어진 배열은 오름차순으로 정렬된 배열을, 특정 인덱스를 기점으로 회전시킨 배열입니다.
* 회전 예시 : [0, 1, 2, 3, 4] -> 인덱스2를 기준으로 회전 -> [2, 3, 4, 0, 1]
주어진 값을 배열에서 찾고, 그 때의 인덱스를 반환하세요.
단, 작성한 코드의 시간 복잡도는 반드시 Big-O(logN)이어야 합니다.
살펴보기
주어진 조건( Big-O(logN) )을 만족하려면 선형탐색을 해선 안되고, 최악의 경우 BIg-O(logN)의 시간복잡도를 가지는 탐색법인 이분 탐색을 사용하는 것이 좋을 것 같다.
배열이 회전한 상태이므로 이분탐색에 약간 변형을 주어야 한다...
일단 시작은 기존의 이분탐색과 같다.
1. 배열에서 중간값을 고른다.
2. 중간값이 찾는 값인지 확인한다.
같으면 반복을 멈추고, 같지 않으면 다음 단계를 진행한다.
3. 배열의 왼쪽 끝 값을 중간값과 비교한다.
오름차순으로 정렬이 된 배열에서는 내가 찾는 값이 중간값(pivot)보다 작은지, 큰지 확인한 후
작으면 중간값을 기준으로 왼쪽 부분, 크면 중간값을 기준으로 오른쪽 부분을 기준으로 다시 탐색하면 됐다.
하지만 이번에는 왼쪽 부분과 오른쪽 부분이 어떤 상태인지를 확인해야 한다.
4. 만약 배열의 왼쪽 값이 중간값보다 작다면?
이 경우 중간값을 기준으로 왼쪽 부분이 오름차순으로 정렬되어 있다!
예시) [4, 5, 6, 7, 0, 1, 2]
다만, 오른쪽 부분의 오름차순 정렬은 보장할 수 없다...
예시) [2, 4, 5, 6, 7, 0, 1]
5. 만약, 배열의 왼쪽 값이 중간값보다 크다면?
이 경우는 중간값을 기준으로 오른쪽 부분만 정렬되어 있는 상태이다!
예시) [6, 7, 0, 1, 2, 4, 5]
6. 찾는 값이 오름차순 정렬이 되어있는 쪽에 들어있는지 확인한다.
즉 4번의 경우, 중간값을 기준으로 왼쪽 부분에 찾는 값이 들어있는지 확인해야 한다.
5번의 경우는 중간값을 기준으로 오른쪽 부분에 원하는 값이 들어있는지 확인한다.
만약 찾는 값이 해당 부분에 있으면, 그 부분을 기준으로 다시 탐색을 하면 되고
없다면, 반대쪽 부분을 기준으로 탐색을 반복하면 된다.
예시)
주어진 배열 : [4, 5, 6, 7, 0, 1, 2]
찾아야 하는 값 : 0
1. 우선 중간값을 선택한다.
[4, 5, 6, 7, 0, 1, 2]
가장 왼쪽값 : 4
가장 오른쪽값 : 2
중간값 : 7
2. 중간값이 찾아야 하는 값과 같은지 확인한다.
7 == 0 ?
같지 않으면 다음 단계를 진행해야 한다.
3. 중간값을 왼쪽 값과 비교한다.
4 < 7 ?
중간값이 더 크므로, 중간값의 왼쪽 부분은 오름차순 정렬이 되어있는 상태이다.
4. 왼쪽 부분에 찾아야 하는 값이 있는지 확인한다.
4 < 0 && 0 < 7 ?
조건이 성립하지 않는다... 그러면 반대편인 오른쪽 부분을 기준으로 다시 탐색해야 한다.
가장 오른쪽 값은 그대로이고, 가장 왼쪽 값이 현재 중간값의 다음 값으로 바뀌게 된다.
그 후 중간값을 새로 선택한다.
5. [0, 1, 2]
가장 왼쪽값 = 기존 중간값의 다음값 = 0
가장 오른쪽값 = 2 (변화 없음)
중간값 = 1
이제 2번부터 다시 반복하다 보면 원하는 값을 찾을 수 있다.
풀어보기
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid]==target){
return mid;
} else if(nums[mid]>=nums[left]){
if(target<=nums[mid] && target>=nums[left]){
right = mid-1;
} else {
left = mid + 1;
}
} else {
if(target>=nums[mid] && target<=nums[right]){
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;