DSA Modified Binary Search

Search in Rotated Sorted Array

Binary search a rotated sorted array — one half is always sorted; route the search there.

Medium
Time O(log n) Space O(1)
LeetCode
4 min read
binary-search

Problem#

Sorted-ascending array of distinct values rotated by an unknown pivot. Return the index of target or -1.

Examples#

  • nums = [4,5,6,7,0,1,2], target = 0 → 4
  • nums = [4,5,6,7,0,1,2], target = 3 → -1

Constraints#

  • 1 <= nums.length <= 5000, distinct values.

Hints#

Hint 1
At each step, one of [lo..mid] or [mid..hi] is sorted — search there if target falls in its range.

Approach#

Modified binary search. Compare nums[lo] to nums[mid] to decide which half is sorted. If target lies in the sorted half, search there; else search the other.

Solution#

Search in Rotated Sorted Array
class Solution {
public:
    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]) { // left half sorted
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else { // right half sorted
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
};

Editorial#

A rotated sorted array has exactly two sorted halves meeting at the pivot. The crucial observation: at any mid, [lo..mid] is sorted iff nums[lo] <= nums[mid]. Once you know which half is sorted, decide whether target belongs to that half by simple range check, otherwise route the search into the other half.

Complexity#

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

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.