0027MediumArrayBinary Search

Shifted Catalogue Lookup

Tracked in this browser only

Trains the technique from

LeetCode 33Search in Rotated Sorted Array

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def locate_card(cards: list[int], wanted: int) -> int:

Java

public int locateCard(int[] cards, int wanted)

The intended approach

Time O(log n)Space O(1)

Halve the drawer as usual, but first work out which side of the midpoint is still cleanly increasing by comparing the midpoint card against the card at the low edge. Exactly one side always is, because the move created a single step down. If the wanted number falls inside that clean side's range then keep that side, otherwise the answer can only be on the other side, and either way half the drawer disappears each round.

Pythonentry point: locate_card

def locate_card(cards, wanted):
    low = 0
    high = len(cards) - 1
    while low <= high:
        mid = (low + high) // 2
        if cards[mid] == wanted:
            return mid
        if cards[low] <= cards[mid]:
            if cards[low] <= wanted < cards[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if cards[mid] < wanted <= cards[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

The obvious version

Read every card front to back and return the first index whose number matches, or -1 after running out. O(n), no halving.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_locate_card(cards, wanted):
    for i in range(len(cards)):
        if cards[i] == wanted:
            return i
    return -1

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in