[5,6,7,1,2,3,4]
와 같이 오름차순 배열을 임의의 숫자만큼 회전시킨, rotated sorted array
가 주어집니다. 이 배열에 주어진 target
이 있다면 index를, 없다면 -1을 반환하는 문제입니다. 설명의 편의를 위해 rotated 되기 전 오름차순의 시작점을 시작점
이라 하겠습니다.
먼저 배열이 rotate 되어있는지 아닌지 nums[start] < nums[end]
조건문으로 판단합니다. rotate 되어있지 않다면 일반적인 binary search를 실시합니다.
rotate 되어있다면 시작점
이 배열의 왼편에 있는지 오른편에 있는지 nums[start] > nums[mid]
조건문으로 판단합니다. 이 조건이 참일때만, 시작점
이 배열의 왼편에 있는 것입니다. start부터 mid까지의 오름차순이 깨져있으니까요.
ex)
[6,7,1,2,3,4,5] 에서 6보다 2가 크니까시작점
인1
이 배열의 왼편에 위치합니다.
이 때 target
이 배열의 왼편에 있는지 오른편에 있는지, nums[start] <= target || target <= nums[mid]
조건문으로 판단합니다. 이 조건이 참일때만, 'target'이 배열의 왼편에 있는겁니다.
시작점
오른편에 있을 때도 비슷한 논리로 진행하시면 됩니다.
class Solution {
public int search(int[] nums, int target) {
int start = 0;
int end = nums.length -1;
int mid = 0;
while (end - start > 1) {
mid = start + (end - start) / 2;
// not rotated
if (nums[start] < nums[end]) {
if (target <= nums[mid]) {
end = mid;
continue;
} else {
start = mid;
continue;
}
}
// 시작점이 왼편
if (nums[start] > nums[mid]) {
if (target >= nums[start] || target <= nums[mid]) {
end = mid;
continue;
} else {
start = mid;
continue;
}
// 시작점이 오른편
} else {
if (target >= nums[mid] || target <= nums[end]) {
start = mid;
continue;
} else {
end = mid;
continue;
}
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
}