문제

https://leetcode.com/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• O(log n)의 시간 복잡도로 문제를 해결해야 하므로 전체를 순회하여 답을 구할 수는 없음 => 이분탐색 활용
• [0, 1, 2, 4, 5, 6, 7]을 3에서 회전한 [4, 5, 6, 7, 0, 1, 2]에서 x를 찾는다고 가정했을 때, 발생할 수 있는 구간을 생각해보면
  1. [4, 5, 6, 7], [0, 1, 2]와 같이 정렬된 구간이 주어진 경우 => x가 첫 번째 수 이상이고, 마지막 수 이하라면 이분탐색 진행
  2. [6, 7, 0, 1, 2]와 같이 정렬된 구간이 섞여있는 경우 => x가 첫 번째 수 이상이거나, 마지막 수 이하라면 이분탐색 진행

코드

class Solution {
    private static int answer;

    public int search(int[] nums, int target) {
        answer = -1;
        binarySearch(nums, target, 0, nums.length - 1);
        return answer;
    }

    private void binarySearch(int[] nums, int target, int left, int right) {
        if (answer != -1) return;
        if (left > right) return;

        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            answer = mid;
            return;
        }
        
        if (mid != 0) {
            if ((nums[left] <= target && nums[mid - 1] >= target) ||
                (nums[left] > nums[mid - 1] && (nums[left] <= target || nums[mid - 1] >= target))) {
                binarySearch(nums, target, left, mid -1);
            }
        }
        if (mid != nums.length - 1) {
            if ((nums[mid + 1] <= target && nums[right] >= target) ||
                (nums[mid + 1] > nums[right] && (nums[mid + 1] <= target || nums[right] >= target))) {
                binarySearch(nums, target, mid + 1, right);
            }
        }
    }
}

결과