Binary Search

A list of whole numbers is sorted from smallest to largest, with no number repeated. Write binary_search(nums, target) that returns the index of target in nums, or -1 if it is not in the list.

Checking every item works, but aim higher: even in a list of a million numbers, the target can be found (or ruled out) in about 20 looks.

Examples

binary_search([1, 3, 5, 7, 9, 11], 7)   # returns 3
binary_search([1, 3, 5, 7, 9, 11], 4)   # returns -1
binary_search([-8, -2, 0, 4], -8)       # returns 0
binary_search([], 5)                    # returns -1

In the first example, 7 sits at index 3 (indexes start at 0).

Constraints

• 0 <= len(nums) <= 100,000
• The numbers in nums are all different and sorted in ascending order

Note

Try it without nums.index() or the in operator: both look at the items one by one.