[LeetCode] 33. Search in Rotated Sorted Array

[Medium] 33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

문제 설명

어느 시점을 기준으로 반전이 되어 있는 정렬된 리스트가 주어진다. 해당 리스트에서 찾고자 하는 값을 O(logn)으로 구해야 한다.

나의 풀이

O(logN)

1. O(logN)의 경우 Binary Search를 이용하면 풀 수 있다.
2. 문제에서 제공하는 Rotated되는 시점을 잡기 위해 조건을 추가한다.
   • target이 num[0]과 num[i] 사이에 있고 num[0] <= num[i]일 경우 : 0~i 범위에서 binary search를 수행한다.
   • target이 num[0]과 num[i] 사이에 있고 num[0] > num[i]일 경우 : target이 num[i]보다 작기 때문에, rotated되는 위치를 찾아야 한다
   • target이 num[i]보다 크고, num[0] > num[i]일 경우 : i~end 범위에서 binary search를 수행한다. 무식한 if문의 나열 후 Discuss에서 XOR을 이용해 깔끔하게 정리한 것을 보고 차용(?)했다. 무식하게 풀다

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high){
            int mid = (low + high) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])){
                low = mid+1;
            }else{
                high = mid;
            }
        }
        return low == high && nums[low] == target ? low : -1;
    }
}