#26 · Binary Search

Search in Rotated Sorted Array

A sorted array of distinct values was rotated at an unknown pivot. Given a target, return its index, or −1 if it is absent, in O(log n) time.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Rotated sorted array

Two ascending runs placed back to back: every value in the second run is smaller than every value in the first. At any midpoint, at least one of the two halves of a window contains no rotation point and is therefore fully sorted.

Memory layout

A contiguous array with O(1) index access, which binary search needs.

Operation	Cost
linear search	O(n)
binary search with a half-sorted check	O(log n)

Binary search with a "which half is sorted" test

Compare nums[left] with nums[mid]. If left ≤ mid, the left half is sorted and a simple range test (is the target between its ends?) decides whether to keep it. Otherwise the right half is sorted and the same test applies there.

Memory layout

Three integers (left, mid, right); window halves each step.

Operation	Cost
search	O(log n) time, O(1) space

Why it fits

A window of a rotated array has at most one rotation point, so one of its halves is always an ordinary sorted array where a range check is exact.
That range check lets us throw away half of the window every step, even though the array as a whole is not sorted: O(log n).
Distinct values make "left ≤ mid" a reliable test for "left half is sorted"; with duplicates it becomes ambiguous.

Why alternatives degrade

Linear scan:: O(n); the problem requires O(log n).
Plain binary search:: The array as a whole is not monotonic, so comparing the target with nums[mid] says nothing about which side to keep.
Un-rotate then search:: Copying the array into sorted order costs O(n).

Four approaches, from naive to production

1 · beginner

Linear scan

time O(n)space O(1)

Check every element in order and return the index of the first match.

int search(vector<int>& nums, int target) {
    for (int i = 0; i < (int)nums.size(); i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

public int search(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target: return i
    return -1

function search(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}

Flaws & bottlenecks

Does not use the sorted structure at all.
Fails the O(log n) requirement.
Always reads up to n elements for a missing target.

Interviewer cross-questions

How can the sorted order help?

Say: Compare against the middle element: in a normal sorted array that rules out half of the array. In a rotated array one of the two halves is still sorted, which is enough.

What if the target is missing?

Say: The scan reads all n elements and returns −1.

Is a linear scan ever the right answer?

Say: For small arrays (a few dozen elements) it is as fast as anything else, due to cache effects, and it is trivially correct.

2 · intermediate

Find the rotation point, then binary search

time O(log n)space O(1)

Binary-search the index of the minimum (the rotation point). The target can only be in the first or the second run; run an ordinary binary search on the correct one.

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

public int search(int[] nums, int target) {
    int n = nums.length;
    int left = 0;
    int right = n - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else right = mid;
    }
    int pivot = left;
    if (n > 0 && target >= nums[pivot] && target <= nums[n - 1]) {
        left = pivot;
        right = n - 1;
    } else {
        left = 0;
        right = pivot - 1;
    }
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

def search(nums, target):
    n = len(nums)
    left = 0
    right = n - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]: left = mid + 1
        else: right = mid
    pivot = left
    if n > 0 and target >= nums[pivot] and target <= nums[n - 1]:
        left = pivot
        right = n - 1
    else:
        left = 0
        right = pivot - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target: return mid
        if nums[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) left = mid + 1;
    else right = mid;
  }
  const pivot = left;
  if (target >= nums[pivot] && target <= nums[nums.length - 1]) {
    left = pivot;
    right = nums.length - 1;
  } else {
    left = 0;
    right = pivot - 1;
  }
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Flaws & bottlenecks

Two separate binary searches with 2× the code and two sets of boundary conditions.
The choice of run (the range test on the second run) is easy to get wrong when the array is not rotated (pivot = 0).
Compares and discards in two different styles (mid + 1 / mid in phase 1; mid + 1 / mid − 1 in phase 2).

Interviewer cross-questions

What happens when the array is not rotated?

Say: The pivot is 0, the whole array is the "second run", the range test sends us to it (when the target is in range) and the second search is a normal binary search. If the target is outside the range, the else-branch makes right = −1 and the loop ends immediately with −1.

Is it really O(log n) overall?

Say: Yes: two binary searches, each O(log n). The constant is about twice as large as the single-pass version.

How could you merge the two phases?

Say: Observe that during the search you can always tell which half is sorted. A single pass that checks the target against the sorted half does the job: the next approach.

3 · advanced

One pass: find the sorted half

time O(log n)space O(1)

At each step, one half of the window is sorted. If the target is within that half's range, search it; otherwise search the other half.

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

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

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

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

Flaws & bottlenecks

Four boundary comparisons that are easy to get slightly wrong (< versus ≤ at each end).
Relies on distinct values: with duplicates nums[left] == nums[mid] no longer proves the left half is sorted.
Hard to explain from scratch under interview pressure.

Interviewer cross-questions

Why nums[left] ≤ nums[mid] and not <?

Say: When the window has two elements, mid equals left. The "left half" is then a single element, which is trivially sorted, so equality must count as sorted.

Why target < nums[mid] (strict) on the left side?

Say: We already tested nums[mid] === target and returned, so the target cannot equal nums[mid]. A strict comparison also keeps mid out of the kept half.

What changes with duplicates?

Say: If nums[left] == nums[mid] == nums[right] we cannot tell which half is sorted. The standard fix is to shrink the window by one (left++ or right−−), giving O(n) in the worst case.

4 · expert

Compare through ±∞ for the other run

time O(log n)space O(1)

Treat nums[mid] as its real value when mid and the target are in the same run, and as −∞ or +∞ when they are in different runs. The "virtual" sequence is monotonic, so an ordinary binary search works.

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = (int)nums.size() - 1;
    int first = nums.empty() ? 0 : nums[0];
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        long long num = ((nums[mid] < first) == (target < first)) ? (long long)nums[mid] : (target < first ? LLONG_MIN : LLONG_MAX);
        if (num == target) return mid;
        if (num < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int first = nums.length == 0 ? 0 : nums[0];
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        long num = ((nums[mid] < first) == (target < first)) ? nums[mid] : (target < first ? Long.MIN_VALUE : Long.MAX_VALUE);
        if (num == target) return mid;
        if (num < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

def search(nums, target):
    left = 0
    right = len(nums) - 1
    first = nums[0] if nums else 0
    while left <= right:
        mid = left + ((right - left) >> 1)
        num = nums[mid] if (nums[mid] < first) == (target < first) else (float('-inf') if target < first else float('inf'))
        if num == target: return mid
        if num < target: left = mid + 1
        else: right = mid - 1
    return -1

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  const first = nums[0];
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    const num = (nums[mid] < first) === (target < first) ? nums[mid] : (target < first ? -Infinity : Infinity);
    if (num === target) return mid;
    if (num < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Flaws & bottlenecks

Clever but opaque: the idea is hard to see until you picture the two runs.
Needs a wide type (or doubles) for the ±∞ sentinels so they cannot collide with real values.
Relies on distinct values and on nums[0] to tell the runs apart.

Interviewer cross-questions

Why does comparing with ±∞ work?

Say: If the target is in the first (larger) run, every element of the second run is "bigger" in index order (+∞), so the sequence reads real values then +∞s, which is ascending. If the target is in the second run, every first-run element acts as −∞, giving −∞s then real values: also ascending. Binary search needs exactly that.

How do you tell which run an element belongs to?

Say: Compare with nums[0]. Elements ≥ nums[0] are in the first run; smaller ones are in the second. This holds for a rotated array of distinct values (and when not rotated, every element is in the first run).

Is it better than the half-sorted version?

Say: It has one uniform loop with a single comparison, so it is shorter and has fewer boundary mistakes to make; but the half-sorted version is easier to explain to an interviewer. Pick the one you can defend.

Synchronized code walkthrough

Showing: Linear scan — shares the player above; click any step to jump.

int search(vector<int>& nums, int target) {
    for (int i = 0; i < (int)nums.size(); i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

public int search(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target: return i
    return -1

function search(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}

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

public int search(int[] nums, int target) {
    int n = nums.length;
    int left = 0;
    int right = n - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else right = mid;
    }
    int pivot = left;
    if (n > 0 && target >= nums[pivot] && target <= nums[n - 1]) {
        left = pivot;
        right = n - 1;
    } else {
        left = 0;
        right = pivot - 1;
    }
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

def search(nums, target):
    n = len(nums)
    left = 0
    right = n - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]: left = mid + 1
        else: right = mid
    pivot = left
    if n > 0 and target >= nums[pivot] and target <= nums[n - 1]:
        left = pivot
        right = n - 1
    else:
        left = 0
        right = pivot - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target: return mid
        if nums[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) left = mid + 1;
    else right = mid;
  }
  const pivot = left;
  if (target >= nums[pivot] && target <= nums[nums.length - 1]) {
    left = pivot;
    right = nums.length - 1;
  } else {
    left = 0;
    right = pivot - 1;
  }
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

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

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

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

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = (int)nums.size() - 1;
    int first = nums.empty() ? 0 : nums[0];
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        long long num = ((nums[mid] < first) == (target < first)) ? (long long)nums[mid] : (target < first ? LLONG_MIN : LLONG_MAX);
        if (num == target) return mid;
        if (num < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int first = nums.length == 0 ? 0 : nums[0];
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        long num = ((nums[mid] < first) == (target < first)) ? nums[mid] : (target < first ? Long.MIN_VALUE : Long.MAX_VALUE);
        if (num == target) return mid;
        if (num < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

def search(nums, target):
    left = 0
    right = len(nums) - 1
    first = nums[0] if nums else 0
    while left <= right:
        mid = left + ((right - left) >> 1)
        num = nums[mid] if (nums[mid] < first) == (target < first) else (float('-inf') if target < first else float('inf'))
        if num == target: return mid
        if num < target: left = mid + 1
        else: right = mid - 1
    return -1

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  const first = nums[0];
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    const num = (nums[mid] < first) === (target < first) ? nums[mid] : (target < first ? -Infinity : Infinity);
    if (num === target) return mid;
    if (num < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}