leetcode 33 java

/*
배열 nums는 오름차순으로 정렬된 정수 배열이며(중복값 없음), 함수에 전달되기 전에 nums는 알 수 없는 피벗 인덱스 k에서 회전될 수 있습니다
(1 <= k < 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) 시간 복잡도를 가져야 합니다.
*/

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int result = -1;

        while(left <= right) {
            int middle = (left+right)/2;

            if(nums[middle] == target) {
                result = middle;
                break;
            }

            if(nums[left] <= nums[middle]) {
                if(nums[left] <= target && nums[middle] >= target) {
                    right = middle-1;
                }
                else {
                    left = middle+1;
                }
            }
            else {
                if(nums[middle] <= target && nums[right] >= target) {
                    left = middle+1;
                }
                else {
                    right = middle-1;
                }
            }
        }
        
        return result;
    }
}

 

정렬되지는 않았지만, 어느 한부분에서 앞뒤로 정렬 되어 있는 것을 이용하는 문제이다.

 

1. 왼쪽이 정렬된 구역이 라면

2. 오른쪽이 정렬된 구역이라면

 

으로 첫번째 분기가 나뉜다. 즉, 정렬된 부분에서 해당값을 찾고 없으면 반대쪽 binarySearch 를 진행하는 것이 핵심이다.

만약 정렬된 부분에서 값이 있다면 정렬된 부분의 이진탐색 진행한다.

 

하지만 여기서 정렬된 부분에서 값이 있다는 것을 단순히 브루트포스 탐색하면서 찾는것이 아니라.

맨 앞과 뒤를 비교해서 찾는다 .

 

예를들어 좌측 이진탐색구역이 1,2,3,4 이고 내가 찾는 target 값이 3이라고 가정했을때,

1 <= target <= 4 로 내가 찾는 값이 좌측에 속해있을 수도 있겠구나 하는 것을 알수 있다.

 

바이너리서치기 때문에 시간 복잡도는 o(logn) 이다