easyBinary search target 15 min
Binary search
The list nums holds different integers in order from smallest to largest. Find target in it and return its position (index). When target does not appear, return -1.
Each call must take O(log n) time, where n is the length of the list and log n is how many times n can be halved before it reaches 1. For a million numbers that is about 20 looks, so you cannot check every number.
Example 1
Input
nums = [-4, 0, 2, 5, 8, 13], target = 5Output3nums[3] is 5.
Example 2
Input
nums = [-4, 0, 2, 5, 8, 13], target = 6Output-16 would sit between 5 and 8, but it is not in the list.
Constraints
0 ≤ len(nums) ≤ 105
-109 ≤ nums[i], target ≤ 109
numsis sorted in ascending order with no repeats.Each call: O(log n) time.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.