Locate a Catalog Number
EasyBinary SearchFree
Problem
A warehouse keeps its product catalog numbers in an array codes, sorted in strictly increasing order. Given a catalog number target, return the index where it is stored, or -1 if the warehouse does not carry it.
Your solution must run in O(log n) time.
Example 1
- Input:
- codes = [3, 8, 15, 21, 40], target = 21
- Output:
- 3
codes[3] = 21.
Example 2
- Input:
- codes = [3, 8, 15, 21, 40], target = 10
- Output:
- -1
10 would sit between 8 and 15, but it is not in the catalog.
Constraints
- 0 ≤ codes.length ≤ 10^5
- -10^9 ≤ codes[i], target ≤ 10^9
- codes is strictly increasing.
Hint
Show the first hint
Compare target with the middle element. What does the comparison tell you about the half you can ignore?
Walkthrough
How to approach it
01Clarify before coding
- Can the array be empty? Yes: return -1 straight away (the loop handles it naturally).
- Can values repeat? No, the array is strictly increasing, so the answer is unique.
- What if target is missing? Return -1.
02Brute force
Scan the array from left to right and return the first index whose value equals target.
Cost: O(n) time, O(1) space. It ignores the ordering entirely; with 10^5 elements and many queries that is wasted work, and the statement asks for O(log n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.