386. Shelf Finder
A small library keeps its catalogue numbers on one long shelf, sorted from the smallest number to the largest, and no number appears twice. A visitor asks for the book with catalogue number target.
Given the sorted array nums of catalogue numbers on the shelf, return the 0-indexed position at which target stands, or -1 if the shelf does not hold it. Walking the whole shelf is too slow when it holds a hundred thousand books, so look for an approach that needs only O(log n) comparisons and O(1) extra space.
Example 1
- Input:
- nums = [3,8,15,22,40], target = 22
- Output:
- 3
- Explanation:
The number 22 stands at index 3.
Example 2
- Input:
- nums = [5,9,12], target = 7
- Output:
- -1
- Explanation:
There is no 7 on the shelf, so the answer is -1.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i], target ≤ 109nums is strictly increasing.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)