Binary Search on Sorted List

Problem

Find the index of target in a sorted list using binary search.

Repeatedly halve the search range: compare the middle element with target and move the low or high pointer accordingly. When duplicates exist, any matching index is acceptable and this implementation returns the first midpoint that matches.

Return -1 when target is absent.

Hint

Keep lo <= hi and discard the half that cannot contain the target.

Test cases

case 1

in: [[-1,0,3,5,9,12],9]

expected: 4

case 2

in: [[-1,0,3,5,9,12],2]

expected: -1

case 3

in: [[],1]

expected: -1

case 4

in: [[5],5]

expected: 0

case 5

in: [[2,2,2],2]

expected: 1

Starter codePython

def binary_search(nums, target):
    # Your code here
    pass

5 test cases · run your code against them in the editor