Search a rotated sorted array

Medium25 minFree, no account

Binary search where half the usual reasoning no longer holds.

The question

A sorted array has been rotated at an unknown pivot. Find the index of a target in O(log n), or -1.

Then: what changes if duplicates are allowed?

search([4,5,6,7,0,1,2], 0)   // 4
search([4,5,6,7,0,1,2], 3)   // -1
search([1], 0)               // -1

25:00Commit to an answer before you open the solution. Reading it first teaches you to recognise good answers, which is not the skill being tested.

Stuck?

0 of 3 hints taken

The worked solution

written by a person · not a grade

Score yourself

0 of 4 marked

Identified and stated the sorted-half invariant30
Correct boundary conditions, verified by hand on small inputs30
True O(log n) with no scanning20
Explained the duplicate case and why it degrades to O(n)20

We run no AI here and nothing on this page grades you. The score is yours, and the useful number is the one you get on the same problem a month from now, cold.

kept in this browser only