Search in Rotated Sorted Array — Half-Sorted Check

Problem 310 · Search in Rotated Sorted Array

Difficulty: Medium · Pattern: Rotated Array BS

Intuition

One of the two halves is always sorted. Check which half, then determine if target falls in the sorted half.

Solutions

# Python
def search(nums, target):
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if nums[mid] == target: return mid
        if nums[lo] <= nums[mid]:  # left half sorted
            if nums[lo] <= target < nums[mid]: hi = mid-1
            else: lo = mid+1
        else:  # right half sorted
            if nums[mid] < target <= nums[hi]: lo = mid+1
            else: hi = mid-1
    return -1

// Java
public int search(int[] nums, int target) {
    int lo=0, hi=nums.length-1;
    while (lo<=hi) {
        int mid=lo+(hi-lo)/2;
        if (nums[mid]==target) return mid;
        if (nums[lo]<=nums[mid]) {
            if (nums[lo]<=target&&target<nums[mid]) hi=mid-1; else lo=mid+1;
        } else {
            if (nums[mid]<target&&target<=nums[hi]) lo=mid+1; else hi=mid-1;
        }
    }
    return -1;
}

// C++
int search(vector<int>& nums, int target) {
    int lo=0, hi=nums.size()-1;
    while (lo<=hi) {
        int mid=lo+(hi-lo)/2;
        if (nums[mid]==target) return mid;
        if (nums[lo]<=nums[mid]) {
            if (nums[lo]<=target&&target<nums[mid]) hi=mid-1; else lo=mid+1;
        } else {
            if (nums[mid]<target&&target<=nums[hi]) lo=mid+1; else hi=mid-1;
        }
    }
    return -1;
}

Complexity

Time: O(log n)
Space: O(1)