LeetCode. 33. Search in Rotated Sorted Array

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

Approach

The array was sorted in ascending order and then rotated, and all values are distinct. At every binary-search step, at least one half of the current interval is sorted. Check whether the target lies within that half’s inclusive value range; if it does, discard the other half, otherwise discard the sorted half. This keeps the target, if present, in the remaining interval. The loop ends when the interval is empty, which also handles an empty input.

The time complexity is O(log N) and the extra space complexity is O(1).

Java

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

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[left] <= nums[mid]) {
                // The left half is sorted.
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // The right half is sorted.
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}