59. Binary Search — Exact Lookup
Search the sorted array for the target value. If it occurs, return a position where it is stored; otherwise return the documented missing-value result.
If multiple positions contain the target, any matching index is valid. Preserve the input and use its sorted order rather than performing a linear scan.
Example 1
Input
[1,3,5,7,9], target=7
Output
3
Explanation: mid=2 is too small; retain [3,5), then compare index 4 and retain [3,4).
Example 2
Input
[2,2,2,2], target=2
Output
Any of 0,1,2,3; this Java method returns 2
Explanation: A first-index oracle would wrongly reject this valid result.
Example 3
Input
[], target=8
Output
−1
Explanation: The initial interval is already empty.
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 1-231 <= target <= 231 - 1- nums is sorted in nondecreasing order; duplicates are allowed.
Hints
Hint 1
What sorted-order fact excludes all values before a midpoint that is too small?
Hint 2
Choose one interval convention and state whether right is an index or a boundary.
Hint 3
Use [0,n), return on equality, otherwise set left=mid+1 or right=mid; an empty interval means absent.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Target at the upper end
[1,3,5,7,9]
7
3