mediumCodingMidSenior

Find the rotation point of a rotated sorted array, then do it again when the array has duplicates.

Binary search for the rotation point by comparing the middle element with the right end. If it is larger, the break lies to the right; otherwise it is at mid or before it. That is O(log n). With duplicates an equal comparison says nothing, so you drop the right end, and the worst case becomes O(n).

4 min readUpdated 2026-10-10Target archetype: Big Tech, Enterprise Captive, Product Startup

Short answer

Binary search for the rotation point against the right end. If a[mid] > a[hi], the order breaks somewhere after mid, so set lo = mid + 1; otherwise the smallest element is at mid or before it, so set hi = mid. That is O(log n) for distinct values. With duplicates, a[mid] == a[hi] tells you nothing, so you drop hi by one, which makes the worst case O(n).

Practice answering out loud

What the interviewer is scoring

Does the candidate define the rotation point precisely, including the unrotated case, before writing the loop
That the comparison is made against the right end, with a reason why the left end cannot separate the cases
Whether hi moves to mid rather than mid minus one, and the loop condition is chosen so it cannot spin
Can they show an input where the equal case is genuinely ambiguous, rather than asserting the linear bound
Whether the duplicate version is tested on the returned index, not only on the value at that index

You have 2 more free pages. Create a free account for unlimited access.

Was this answer helpful?

Likely follow-ups

The array was rotated right by an unknown k. Recover k from the rotation point, and say what k means if the array has duplicates.
How would you find the maximum instead, and does the right-end comparison still work?
The array is all equal except one smaller value. Trace your duplicate-safe loop on it and count the steps.
Your caller now wants every target lookup to be O(log n) after one preprocessing pass. What do you store?

Related Topics

#binary-search

What the rotation point is

A rotated array is a sorted array shifted cyclically: 1 2 3 4 5 becomes 3 4 5 1 2. The rotation point is the index where the order breaks, the one position r where a[r-1] > a[r]. Here it is index 3, holding the minimum. If the array was never rotated there is no break, and the rotation point is 0 by convention. For a right rotation by k, the rotation point is k.

Say that definition before coding. It settles the unrotated case, and it makes the duplicate version testable later. The neighbouring page on searching a rotated sorted array finds a target directly; finding the break first is the reusable primitive behind it.

Why you compare against the right end

The invariant is that the answer lies in [lo, hi]. You need one comparison at mid that tells you which side to keep.

Comparing with the left end does not work. In 1 2 3 4 5 and in 3 4 5 1 2, a[lo] <= a[mid] holds both times. In the first the answer is at lo; in the second it is to the right of mid. One comparison, two different answers.

The right end separates the cases. If a[mid] > a[hi], mid sits in the higher run and hi in the lower run, so the break is in (mid, hi]. If a[mid] < a[hi], everything from mid to hi is in order. The break is then at mid or to its left, and mid itself may be the minimum. That is why hi = mid, not mid - 1.

int rotationPoint(int[] a) { // distinct values int lo = 0, hi = a.length - 1; while (lo < hi) { // not <=: with hi = mid, lo == hi would never exit int mid = lo + (hi - lo) / 2; // mid < hi always, so hi = mid still shrinks the range if (a[mid] > a[hi]) lo = mid + 1; else hi = mid; } return lo; }

The loop condition and the update must be chosen together. Floor division keeps mid strictly below hi, so hi = mid always shrinks the range. With lo <= hi, the range of one element would loop forever. Each step halves the range, so the binary search runs in O(log n).

Duplicates return the right value at the wrong index

This is the part most answers miss. Plain hi-- finds the minimum value, but it can return the wrong rotation point. Take 1 1 1 2 1. The break is at index 4, because 2 > 1. The loop sees a[2] == a[4], drops index 4, and ends up returning index 0. a[0] is also a 1, so a test that checks only the value passes. A caller using that index to undo the rotation gets 1 1 1 2 1 back, which is not sorted.

The fix is one check before you discard hi. If a[hi - 1] > a[hi], then hi is the break, so return it.

int rotationPointWithDuplicates(int[] a) { int lo = , hi = a.length - ; (lo < hi) { lo + (hi - lo) / ; (a[mid] > a[hi]) lo = mid + ; (a[mid] < a[hi]) hi = mid; { (a[hi - ] > a[hi]) hi; hi--; } } lo; }

Why is that enough? In a rotated non-decreasing array there is at most one break. hi-- discards only index hi, so the break survives in range unless it was hi, and the check catches exactly that case. If there is no break at all, lo never moves, because it moves only when a[mid] > a[hi], and the answer 0 comes out.

Test it the way the bug hides: brute-force the answer on small random rotated array inputs with values drawn from {0, 1, 2}, and compare indices, not values. Comparing values passes the broken version.

In a rotated array, compare mid with the right end and keep mid in range. With duplicates, accept the linear worst case, and check that the element you are about to drop is not the break itself.

Find the rotation point of a rotated sorted array, then do it again when the array has duplicates.

Short answer

What the interviewer is scoring

Was this answer helpful?

Likely follow-ups

Related questions

Related Topics

What the interviewer is scoring

What the rotation point is

Why you compare against the right end

Duplicates make the equal case blind

Duplicates return the right value at the wrong index

Find the rotation point of a rotated sorted array, then do it again when the array has duplicates.

Answer

Short answer

What the interviewer is scoring

Was this answer helpful?

Likely follow-ups

Related questions

Related Topics

What the interviewer is scoring

What the rotation point is

Why you compare against the right end

Duplicates make the equal case blind

Duplicates return the right value at the wrong index