Shifted Binary Search

Tags

Shifted Binary Search

Category

Searching

Difficulty

Hard

Problem Statement

Given a sorted array of distinct integers that has been rotated by some unknown amount (e.g., [45, 61, 71, 72, 1, 5, 17, 33]), and a target value, find the index of the target in the array. If the target is not present, return -1. The algorithm must run in O(log n) time.

Intuition

Even though the array is rotated, at least one half of any subarray (left or right of mid) is guaranteed to be in sorted order. By identifying which half is sorted, we can determine whether the target lies within that sorted half and decide which half to search. This preserves the halving property of standard binary search.

Approach

  1. Initialize left = 0 and right = length - 1.
  2. While left <= right:
    • Compute mid = left + (right - left) / 2.
    • If array[mid] == target, return mid.
    • Determine which half is sorted:
      • Left half is sorted (array[left] <= array[mid]):
        • If target >= array[left] and target < array[mid], search left: right = mid - 1.
        • Otherwise, search right: left = mid + 1.
      • Right half is sorted (array[mid] <= array[right]):
        • If target > array[mid] and target <= array[right], search right: left = mid + 1.
        • Otherwise, search left: right = mid - 1.
  3. Return -1 if not found.

Pseudocode

function shiftedBinarySearch(array, target):
    left = 0
    right = length(array) - 1
    while left <= right:
        mid = left + (right - left) / 2
        if array[mid] == target:
            return mid
        if array[left] <= array[mid]:
            // Left half is sorted
            if target >= array[left] and target < array[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            // Right half is sorted
            if target > array[mid] and target <= array[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Time & Space Complexity

  • Time: O(log n) — The search space is halved at every step, identical to standard binary search.
  • Space: O(1) for the iterative version. O(log n) for a recursive version.

Key Insights

  • The key insight is that in a rotated sorted array, at least one half around mid is always perfectly sorted.
  • The condition array[left] <= array[mid] determines whether the left half is sorted. Using <= (not <) handles the case where left == mid.
  • Distinct integers are assumed, which simplifies the sorted-half detection. With duplicates, worst-case degrades to O(n).
  • This technique also applies to finding the minimum element in a rotated sorted array and related problems.

Edge Cases

  • Array is not rotated (rotation by 0) — standard binary search behavior.
  • Array has a single element — one comparison.
  • Target is the pivot element (the smallest element in the rotated array) — found by the sorted-half logic.
  • Target is not in the array — pointers cross and -1 is returned.
  • Rotation by length - 1 positions — the array looks nearly sorted in reverse at the boundary; the algorithm handles it correctly.

Linked mentions