Binary Search
EasyBinary Search
You are given an array of integers nums sorted in ascending order with no duplicates, and an integer target.
Return the index of target in nums, or -1 if target is not in the array. Indices start at 0.
Your algorithm must run in O(log n) time, so a linear scan is not acceptable.
Example 1
- Input:
- nums = [-2,0,4,7,11], target = 7
- Output:
- 3
- Explanation
- The middle element is 4, which is too small, so only the right half
[7, 11]can hold 7. Checking there finds it at index 3.
Example 2
- Input:
- nums = [-2,0,4,7,11], target = 5
- Output:
- -1
- Explanation
- 5 would sit between 4 (index 2) and 7 (index 3). The search range shrinks to nothing without a match, so the answer is -1.
Example 3
- Input:
- nums = [7], target = 7
- Output:
- 0
- Explanation
- The only element matches, so its index, 0, is returned.
Constraints
1 <= nums.length <= 10^4-10^4 < nums[i], target < 10^4- All values in
numsare unique numsis sorted in ascending order