SimuVedaAlgorithms Lab Open in the lab

Searching / Intermediate

Search in a Rotated Sorted Array Visualizer

Cut at the middle. One of the two halves is always fully sorted, and you can tell which by comparing its ends. If the target lies inside that sorted half, search there; otherwise search the other half.

Start the Search in a Rotated Sorted Array simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(log n)
Worst timeO(log n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Search for 5. The values rise, drop once, then rise again. [15, 18, 22, 30, 41, 2, 5, 8, 11]
  2. The middle of [0..8] is index 4, value 41.
  3. a[lo] = 15 ≤ a[mid] = 41, so the left half is sorted.
  4. 5 is not between 15 and 41, so search the right half.
  5. The middle of [5..8] is index 6, value 5.
  6. 5 is the target. Found at index 6.

Try it with your own input →

Search in a rotated sorted array in Java, Python, C++, C and JavaScript

int search(int[] a, int t) {
  int lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == t) return mid;
    if (a[lo] <= a[mid]) {
      if (a[lo] <= t && t < a[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (a[mid] < t && t <= a[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}
def search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == t:
            return mid
        if a[lo] <= a[mid]:
            if a[lo] <= t < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if a[mid] < t <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1
int search(const vector<int>& a, int t) {
  int lo = 0, hi = (int)a.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == t) return mid;
    if (a[lo] <= a[mid]) {
      if (a[lo] <= t && t < a[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (a[mid] < t && t <= a[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}
int search(int a[], int n, int t) {
  int lo = 0, hi = n - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == t) return mid;
    if (a[lo] <= a[mid]) {
      if (a[lo] <= t && t < a[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (a[mid] < t && t <= a[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}
function search(a, t) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] === t) return mid;
    if (a[lo] <= a[mid]) {
      if (a[lo] <= t && t < a[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (a[mid] < t && t <= a[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

In an interview

LeetCode 33, Search in Rotated Sorted Array: a sorted array was turned at an unknown point. Find the target in O(log n).

Compare a[lo] <= a[mid] (with the equals) so a two-value window works. With duplicates (LeetCode 81) you sometimes cannot tell which half is sorted, and the worst case becomes O(n).

More searching