[C] LeetCode 33. Search in Rotated Sorted Array

문제 

번역

서로 다른 값으로 이루어진 정수 배열 nums가 있다.

이 배열은 원래 오름차순으로 정렬되어 있다.

함수에 전달되기 전에, nums는 알 수 없는 인덱스 k(k는 1 이상 nums.length 미만)에서 왼쪽으로 회전되었을 수도 있다.

 

회전된 배열은 다음과 같은 형태가 된다.

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

 

인덱스는 0부터 시작한다.

예를 들어 [0,1,2,4,5,6,7] 배열이 왼쪽으로 3칸 회전하면 [4,5,6,7,0,1,2]가 된다.

 

회전되었을 수도 있는 배열 nums와 정수 target이 주어졌을 때, target이 nums안에 있으면 그 인덱스를 반환하고 없으면 -1를 반환해라.

알고리즘의 시간복잡도는 반드시 \(O(\log{n})\)이어야 한다.

 

접근 방법과 소스 코드

어떤 중간 인덱스 m이 있다고 해보자.

m을 기준으로 배열의 반을 나누면 왼쪽 배열이나 오른쪽 배열 둘 중 하나는 적어도 반드시 정렬되어 있는 상태이다.

정렬된 구간에 타겟이 들어갈 수 있는지 판단하고 들어가면 해당 배열로, 들어가지 않는다면 반대쪽으로 이동해서 확인한다.

그러다가 타겟값을 찾으면 해당 인덱스를 반환하고 못찾으면 -1을 반환하면 된다.

 

int search(int* nums, int numsSize, int target) {
    int l = 0, r = numsSize - 1;
    while(l <= r) {
        int m = (l+r)/2;
        if(nums[m] == target) return m;
        if(nums[l] <= nums[m]) {
            if(nums[l] <= target && target <= nums[m]) r=m-1;
            else l=m+1;
        } else {
            if(nums[m] <= target && target <=nums[r]) l=m+1;
            else r=m-1;
        }
    }
    return -1;
}

 

순서가 정렬이 안된 부분에 대해서만 잘 고민하면 되는거 같다.