Search in Rotated Sorted Array — Modified Binary Search O(log n) [Google, Meta, Amazon]

Problem Statement

An integer array nums sorted in ascending order is rotated at some pivot. Given the rotated array and a target, return its index or -1.

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

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(log n) time, O(1) space

Intuition

At every mid, one half is always sorted. Check if target is in the sorted half; if yes, narrow there; else go other half.

if nums[l] <= nums[mid]:  # left half sorted
    if nums[l] <= target < nums[mid]: r = mid-1
    else: l = mid+1
else:  # right half sorted
    if nums[mid] < target <= nums[r]: l = mid+1
    else: r = mid-1

C++ Solution

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0, r=(int)nums.size()-1;
        while (l<=r) {
            int mid=l+(r-l)/2;
            if (nums[mid]==target) return mid;
            if (nums[l]<=nums[mid]) {
                if (nums[l]<=target && target<nums[mid]) r=mid-1;
                else l=mid+1;
            } else {
                if (nums[mid]<target && target<=nums[r]) l=mid+1;
                else r=mid-1;
            }
        }
        return -1;
    }
};

Java Solution

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

Python Solution

def search(nums, target):
    l, r = 0, len(nums)-1
    while l <= r:
        mid = (l+r)//2
        if nums[mid] == target: return mid
        if nums[l] <= nums[mid]:
            if nums[l] <= target < nums[mid]: r = mid-1
            else: l = mid+1
        else:
            if nums[mid] < target <= nums[r]: l = mid+1
            else: r = mid-1
    return -1

JavaScript Solution

function search(nums, target) {
    let l=0, r=nums.length-1;
    while (l<=r) {
        const mid=l+(r-l>>1);
        if (nums[mid]===target) return mid;
        if (nums[l]<=nums[mid]) {
            if (nums[l]<=target && target<nums[mid]) r=mid-1;
            else l=mid+1;
        } else {
            if (nums[mid]<target && target<=nums[r]) l=mid+1;
            else r=mid-1;
        }
    }
    return -1;
}

Complexity: O(log n) time, O(1) space

Follow-up: Search in Rotated Sorted Array II (with duplicates) — worst case O(n) when nums[l]==nums[mid] (can't determine sorted half, do l++).