Show problems as
Classic problem #33MediumArrayBinary Search

Search in Rotated Sorted Array

Real-world version: Shifted Catalogue Lookup
Tracked in this browser only
Read Search in Rotated Sorted Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A catalogue drawer holds cards stamped with reference numbers, no two alike. Numbering starts below zero for retired stock, so a reference number may be negative.

The cards were filed strictly increasing from front to back. Afterwards a clerk cut the drawer at one point, lifted out the block in front of the cut and set it down behind the remaining block, leaving both blocks in their own order. If the clerk happened to cut right at the very front, nothing actually moved and the drawer is still plainly increasing.

cards is the drawer as it reads today, front to back. Given a reference number wanted, return the index of the card carrying it, or -1 when the drawer holds no such card. Reference numbers never repeat, so at most one index can be the answer.

Pulling a card out to read it is the expensive step, so the number of cards you inspect has to grow only with the logarithm of the drawer size. Working front to back through the drawer is too many reads.

Examples

Example 1

Input
cards = [7, 9, 12, -5, 1, 4], wanted = 1
Output
4

Filed in order the drawer would read -5, 1, 4, 7, 9, 12; the clerk cut before 7 and moved the block -5, 1, 4 to the back. Card 1 now sits at index 4.

Example 2

Input
cards = [-3, 0, 8], wanted = 8
Output
2

The cut fell at the very front, so nothing moved and the drawer still increases throughout. Card 8 is last, at index 2.

Example 3

Input
cards = [7, 9, 12, -5, 1, 4], wanted = 6
Output
-1

The number 6 would slot between 4 and 7 in the filed order, but no card carries it, so the drawer reports nothing.

Constraints

  • 1 <= cards.length <= 5000
  • -10^4 <= cards[i] <= 10^4
  • Every reference number in cards is distinct
  • cards is an increasing filing whose front block may have been moved to the back
  • -10^4 <= wanted <= 10^4
  • The lookup must run in O(log n) time

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def locate_card(cards: list[int], wanted: int) -> int:
Java
public int locateCard(int[] cards, int wanted)

More on the same topics