15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A rotated sorted array has two increasing runs joined at a pivot, so plain binary search directions fail. At each midpoint, find the sorted half by testing A[low] <= A[mid], then check whether the target falls inside that half's range. Keep that half or discard it. For distinct values this takes O(log n) time.
| Precondition | Strictly increasing before rotation, distinct values |
|---|---|
| Left half is sorted | A[low] <= A[mid] |
| Target in sorted left half | A[low] <= target < A[mid] |
| Target in sorted right half | A[mid] < target <= A[high] |
| Time and space | O(log n) worst case, O(1) extra space |
| Duplicates | Not covered, the sorted-half test becomes ambiguous |
The algorithm builds on ordinary binary search.
In an ordinary strictly increasing array, comparing A[mid] with target tells you which side can be discarded. A rotated array has the same values, but the increasing order wraps once at a pivot.
The algorithm assumes:
A was strictly increasing before rotation.[low, high].target, or -1 when target is absent.Duplicate values need a separate specification. They can make it unclear which half is sorted under the test used here.
Write the array with both indices and values.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
A[index] | 6 | 7 | 1 | 2 | 3 | 4 | 5 |
1A = [6, 7, 1, 2, 3, 4, 5]
2target = 2Before rotation, these values were in increasing order:
1[1, 2, 3, 4, 5, 6, 7]The rotation moved the beginning of that order after 7.
Rotated array [6, 7, 1, 2, 3, 4, 5]: the order wraps from 7 down to 1 at the pivot, leaving two increasing runs, [6, 7] and [1, 2, 3, 4, 5].
There are now two increasing runs:
[6, 7][1, 2, 3, 4, 5]The whole array is not increasing from left to right, so ordinary binary-search direction rules do not work by themselves. First determine which half of the current interval is increasing.
Start with the full inclusive interval.
1low = 0
2high = 6Compute the midpoint:
1mid = low + floor((high - low) / 2)
2 = 0 + floor((6 - 0) / 2)
3 = 3Now inspect index 3.
| Name | Value |
|---|---|
low | 0 |
high | 6 |
mid | 3 |
A[mid] | 2 |
target | 2 |
The ordered states are:
low = 0, high = 6, midpoint = 3, A[3] = 2; the target equals the midpoint value.3.No boundary changes are needed. The midpoint already contains the target.
At the start of every iteration:
If
targetoccurs inA, then it lies somewhere in the inclusive interval[low, high].
Also:
Within
[low, high], at least one of[low, mid]or[mid, high]is sorted in increasing order.
The sorted-half fact relies on two conditions:
The interval can contain the pivot or not.
Identify a sorted left half with:
1A[low] <= A[mid]Because values are distinct, the values from low through mid are in increasing order. If that test is false, the right half must be sorted.
For the board example:
1A[low] = A[0] = 6
2A[mid] = A[3] = 2Since 6 <= 2 is false, the left half crosses the pivot. The right half [mid, high] is sorted:
1[2, 3, 4, 5]The target was found before this decision was needed, but the algorithm uses this test after every nonmatching midpoint comparison.
Begin every iteration by checking whether the midpoint is the target.
1if A[mid] == target:
2 return midIf it is not, find the sorted half.
If:
1A[low] <= A[mid]then values in [low, mid] are increasing.
Because A[mid] is not the target, the target belongs in this left half exactly when:
1A[low] <= target < A[mid]The lower comparison is inclusive because the target might be at low.
The upper comparison is strict because a midpoint match was already checked. If target == A[mid], the algorithm would have returned.
If the range test succeeds, retain the left half but exclude mid:
1high = mid - 1Otherwise, discard the left half and mid:
1low = mid + 1Otherwise, [mid, high] is sorted.
The target belongs in that sorted right half exactly when:
1A[mid] < target <= A[high]The comparison with A[mid] is strict because mid did not match.
If the range test succeeds:
1low = mid + 1Otherwise:
1high = mid - 1Each nonmatching iteration removes mid and rejects one side that cannot contain the target.
Function contract
1searchRotatedDistinct(A, target)
2
3Input:
4 A: an array formed by rotating a strictly increasing array of distinct values.
5 target: a value to search for.
6
7Returns:
8 An index i such that A[i] == target, if target occurs.
9 -1 if target does not occur.
10
11Mutation behavior:
12 Does not modify A.
13
14Boundaries:
15 low and high describe an inclusive candidate interval [low, high].11 function searchRotatedDistinct(A, target):
22 low = 0
33 high = length(A) - 1
44
55 while low <= high:
66 mid = low + floor((high - low) / 2)
77
88 if A[mid] == target:
99 return mid
1010
1111 if A[low] <= A[mid]:
1212 # The left half [low, mid] is sorted.
1313 if A[low] <= target and target < A[mid]:
1414 high = mid - 1
1515 else:
1616 low = mid + 1
1717 else:
1818 # The right half [mid, high] is sorted.
1919 if A[mid] < target and target <= A[high]:
2020 low = mid + 1
2121 else:
2222 high = mid - 1
2323
2424 return -1The empty-array case works without a special branch:
1length(A) = 0
2high = -1
3low = 0Then low <= high is false, so line 24 returns -1.
Use the original input:
1A = [6, 7, 1, 2, 3, 4, 5]
2target = 2| Line | Action | State |
|---|---|---|
| 2 | Set low to the first index. | low = 0 |
| 3 | Set high to the last index. | high = 6 |
| 5 | Test whether the interval is nonempty. | 0 <= 6, true |
| 6 | Compute midpoint. | mid = 0 + floor((6 - 0) / 2) = 3 |
| 8 | Compare midpoint value with target. | A[3] == 2, true |
| 9 | Return the midpoint index. | return 3 |
The function stops here. It does not run lines 11 through 22 because an exact match was found.
Assume A is a rotated strictly increasing array with distinct values.
Before the loop begins:
1low = 0
2high = length(A) - 1So [low, high] contains every index in the array. If target occurs, it is in this interval.
Also, the array has at most one rotation pivot. Therefore, in the initial interval, at least one of the two midpoint halves is sorted.
The required facts hold before the first iteration.
Assume that at the start of an iteration:
target occurs, it lies in [low, high];Let mid be the index computed by line 6.
If A[mid] == target, line 9 returns a correct index.
Now consider a nonmatching midpoint.
If A[low] <= A[mid], then [low, mid] is increasing.
In a strictly increasing interval, the target can occur in that half exactly when:
1A[low] <= target < A[mid][low, mid - 1]. Since mid does not match, any occurrence in the left half remains in the retained interval.[mid + 1, high].If the left-half test is false, the right half [mid, high] is sorted.
The target can occur there exactly when:
1A[mid] < target <= A[high][mid + 1, high]. The nonmatching midpoint is correctly excluded.[low, mid - 1].In every nonmatching case, the algorithm preserves any possible target while removing mid and one side of the interval.
The facts therefore hold at the start of the next iteration.
Every nonmatching iteration changes either:
1high = mid - 1or:
1low = mid + 1So the inclusive interval becomes smaller.
Eventually, one of two things happens:
target, and the algorithm returns its index.low > high.If the interval is empty, the invariant says that any possible target would have to be inside [low, high]. There are no indices in that interval, so the target is absent. Returning -1 is correct.
Consider one nonmatching loop iteration.
The retained candidate interval has at most about half as many indices as before.
Starting with n indices, repeated halving gives a logarithmic number of iterations in the worst case:
1n, about n / 2, about n / 4, about n / 8, ...Therefore:
O(log n) for distinct values.O(1) when the first midpoint equals the target, as in the worked example.O(1).The iterative method stores only low, high, mid, and constant temporary values. It does not allocate another array.
Incorrect assumption
1if A[mid] < target:
2 low = mid + 1
3else:
4 high = mid - 1That rule assumes the entire current interval is sorted.
Exposing input
1A = [4, 5, 1, 2, 3]
2target = 5Initially:
1low = 0
2high = 4
3mid = 2
4A[mid] = 1Ordinary binary-search logic sees 1 < 5 and moves right:
1low = 3But 5 is at index 1, which has just been discarded.
Correction
First identify the sorted half. Here, the left half [4, 5, 1] is not sorted, so the right half is sorted. Since 5 is not in the sorted right-half range, retain the left side.
Incorrect line
1if A[low] < target and target < A[mid]:Exposing input
1A = [4, 5, 1, 2, 3]
2target = 4The target is exactly at low.
If the left half is sorted in a later interval and the test uses:
1A[low] < targetthen 4 < 4 is false. The algorithm can discard the side containing index low.
Correction
Use an inclusive lower endpoint:
1A[low] <= target and target < A[mid]The target may equal A[low].
Incorrect assumption
1A[low] <= A[mid]always identifies one unambiguous sorted half, even with repeated values.
Exposing input
1A = [2, 2, 2, 3, 1, 2]
2target = 1Equal endpoint values can make the half classification ambiguous. The distinct-values reasoning no longer guarantees that the same decision rule safely discards half the interval.
Correction
Keep this algorithm for rotated strictly increasing arrays with distinct values. If duplicates are allowed, specify separate duplicate-handling behavior rather than claiming the same half-identification test provides the same logarithmic guarantee.
| Input | Expected result |
|---|---|
A = [], target = 2 | -1 |
A = [4], target = 4 | 0 |
A = [4], target = 1 | -1 |
A = [1, 2, 3, 4], target = 3 | 2; this follows ordinary binary-search behavior because there is no rotation |
A = [4, 5, 1, 2, 3], target = 4 | 0 |
A = [4, 5, 1, 2, 3], target = 3 | 4 |
A = [2, 2, 3, 1, 2], target = 1 | outside this lesson’s distinct-values precondition |
Implement this contract:
1searchRotatedDistinct(A, target)It must:
target;-1 if target is absent;A.Tests will include:
1def search_rotated(a, target):
2 low, high = 0, len(a) - 1
3 while low <= high:
4 mid = low + (high - low) // 2
5 if a[mid] == target:
6 return mid
7 if a[low] <= a[mid]: # left half is sorted
8 if a[low] <= target < a[mid]:
9 high = mid - 1
10 else:
11 low = mid + 1
12 else: # right half is sorted
13 if a[mid] < target <= a[high]:
14 low = mid + 1
15 else:
16 high = mid - 1
17 return -1
18
19print(search_rotated([6, 7, 1, 2, 3, 4, 5], 2))
20print(search_rotated([4, 5, 1, 2, 3], 4))
21print(search_rotated([4, 5, 1, 2, 3], 3))
22print(search_rotated([6, 7, 1, 2, 3, 4, 5], 8))1public class Main {
2 static int searchRotated(int[] a, int target) {
3 int low = 0, high = a.length - 1;
4 while (low <= high) {
5 int mid = low + (high - low) / 2;
6 if (a[mid] == target) return mid;
7 if (a[low] <= a[mid]) { // left half is sorted
8 if (a[low] <= target && target < a[mid]) high = mid - 1;
9 else low = mid + 1;
10 } else { // right half is sorted
11 if (a[mid] < target && target <= a[high]) low = mid + 1;
12 else high = mid - 1;
13 }
14 }
15 return -1;
16 }
17
18 public static void main(String[] args) {
19 System.out.println(searchRotated(new int[]{6, 7, 1, 2, 3, 4, 5}, 2));
20 System.out.println(searchRotated(new int[]{4, 5, 1, 2, 3}, 4));
21 System.out.println(searchRotated(new int[]{4, 5, 1, 2, 3}, 3));
22 System.out.println(searchRotated(new int[]{6, 7, 1, 2, 3, 4, 5}, 8));
23 }
24}1#include <iostream>
2#include <vector>
3using namespace std;
4
5int searchRotated(const vector<int>& a, int target) {
6 int low = 0, high = (int)a.size() - 1;
7 while (low <= high) {
8 int mid = low + (high - low) / 2;
9 if (a[mid] == target) return mid;
10 if (a[low] <= a[mid]) { // left half is sorted
11 if (a[low] <= target && target < a[mid]) high = mid - 1;
12 else low = mid + 1;
13 } else { // right half is sorted
14 if (a[mid] < target && target <= a[high]) low = mid + 1;
15 else high = mid - 1;
16 }
17 }
18 return -1;
19}
20
21int main() {
22 cout << searchRotated({6, 7, 1, 2, 3, 4, 5}, 2) << endl;
23 cout << searchRotated({4, 5, 1, 2, 3}, 4) << endl;
24 cout << searchRotated({4, 5, 1, 2, 3}, 3) << endl;
25 cout << searchRotated({6, 7, 1, 2, 3, 4, 5}, 8) << endl;
26}1function searchRotated(a, target) {
2 let low = 0, high = a.length - 1;
3 while (low <= high) {
4 const mid = low + Math.floor((high - low) / 2);
5 if (a[mid] === target) return mid;
6 if (a[low] <= a[mid]) { // left half is sorted
7 if (a[low] <= target && target < a[mid]) high = mid - 1;
8 else low = mid + 1;
9 } else { // right half is sorted
10 if (a[mid] < target && target <= a[high]) low = mid + 1;
11 else high = mid - 1;
12 }
13 }
14 return -1;
15}
16
17console.log(searchRotated([6, 7, 1, 2, 3, 4, 5], 2));
18console.log(searchRotated([4, 5, 1, 2, 3], 4));
19console.log(searchRotated([4, 5, 1, 2, 3], 3));
20console.log(searchRotated([6, 7, 1, 2, 3, 4, 5], 8));A sorted array is rotated when part of its front moves behind its end. [1, 2, 3, 4, 5, 6, 7] can become [6, 7, 1, 2, 3, 4, 5]. The result has two increasing runs, [6, 7] and [1, 2, 3, 4, 5].
The pivot is where the order wraps, between 7 and 1 in [6, 7, 1, 2, 3, 4, 5]. The search above never needs it, because A[low] <= A[mid] identifies a sorted half directly. To locate the smallest value, binary search by comparing A[mid] with A[high].
This algorithm does not cover it. In [1, 0, 1, 1, 1] with target 0, A[low] <= A[mid] reads the left half as sorted, the search discards it and returns -1. Equal values make the sorted-half test ambiguous, so the O(log n) guarantee no longer holds. Duplicates need their own rule.
The target can sit exactly at low, so that index must stay in range. The midpoint was already compared and did not match, so the test is strict there.
The algorithm is the same for distinct values. This page explains why each comparison is safe, and the editorial covers the interview problem itself.