[Java] LeetCode 33번 Search in Rotated Sorted Array

로테이션이 되어있으면 숫자를 오름차순의 구역 두개의 구역으로 나누어서 생각할 수 있다.  왼쪽의 첫번째가 무조건 첫번째의 숫자가 오른쪽 구역의 첫번째 숫자보다 크게된다. 이 지점을 binary search로 찾는다.

오른쪽 구역의 시작 점을 turnPoint라는 변수에 저장하였다. 이제 왼쪽과 오른쪽 구역에서 각각 일치하는 숫자의 index를 찾고 이것을 return 해주면 된다.

class Solution {
    public int search(int[] nums, int target) {
        int first = nums[0];
        int n = nums.length;
        int l = 1;
        int r = n - 1;
        int turnPoint = 0;
        int answer = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] <= first) {
                turnPoint = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        l = turnPoint;
        r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                answer = mid;
                break;
            }
        }

        l = 0;
        r = turnPoint - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                answer = mid;
                break;
            }
        }

        return answer;
    }
}