문제 설명
정수형 배열 nums가 중복없이 오름차순 정렬되어 있다.
함수를 거치기 전 nums는 임의의 pivot 인덱스 k(1<=k<nums.length)부터 순환될 수 있으므로, 결과 배열은 [nums[k],nums[k+1], ... , nums[n-1], nums[0], nums[1], ..., nums[k-1]]가 된다.
예를 들어, [0,1,2,4,5,6,7] 는 pivot 인덱스 3에서 순환한다면 [4,5,6,7,0,1,2]가 된다.
순환이 완료된 배열 nums가 주어지고 정수 target이 주어지고, nums 안에 존재하는 target의 인덱스를 찾아라.존재하지 않다면 -1을 출력한다.
반드시 시간복잡도 O(logn)으로 구현하시오.
출력예시
접근 방법
첫번째 시도
일반적인 이분탐색에서 0 인덱스의 값도 고려를 해야하지 않을까?
기준을 하나 더 늘려서 구현해본다.
배열은 증가했다가 최소값을 찍고 다시 증가하는 모양이다.
nums[0]을 기준으로 타겟 값이 크다면, 그대로 증가하는 부분에 위치해 있을 것이고
nums[0]을 기준으로 타겟 값이 작다면, 증가 이후 최소 값 인덱스~마지막 인덱스 사이에 존재 할 것 이다.
두 가지로 나눈 후, 이분 탐색에서의 중간값(mid)과 nums[0]을 비교하여 똑같이 어디에 위치할 지 확인한다.
그 후 start와 end 값을 조정하면서 이분 탐색 실시,,,!
소스코드
class Solution {
public:
int search(vector<int>& nums, int target) {
int start=0;
int end = nums.size()-1;
int mid;
if(nums[0] > target){
while(start <= end){
mid = (start + end)/2;
//증가하는 부분에 mid 위치
if(nums[0] <= nums[mid]){
start = mid+1;
}
//증가했다가 감소하는 부분에 mid 위치
else{
if(nums[mid] > target){
end = mid -1;
}
else if(nums[mid] < target){
start = mid+1;
}
else return mid;
}
}
}
else if (nums[0] < target){
while(start<=end){
mid = (start + end)/2;
//증가하는 부분에 mid 위치
if(nums[0] <= nums[mid]){
if(nums[mid] > target){
end = mid -1;
}
else if(nums[mid] < target){
start = mid+1;
}
else return mid;
}
//증가했다가 감소하는 부분에 mid 위치
else{
end = mid - 1;
}
}
}
else return 0;
return -1;
}
};
돌아보기
처음에 문제가 한 번에 이해가 안 갔다... 얼마나 효율적으로 코드를 짤 건지가 관건인 문제였던 듯 함.
실행 시간은 4ms로 나쁘지 않았지만 코드가 너무 더러움 ㅠ
