Binary Search

Problem

Search for target in a sorted list of integers and return its index, or -1 if it is absent.

Use the classic binary search loop: keep low and high pointers, compare the middle element, and halve the remaining range each step. The list is sorted in ascending order.

Hint

Halve the search range each iteration by comparing arr[mid] with the target.

Test cases

case 1

in: [[1,3,5,7,9],5]

expected: 2

case 2

in: [[1,3,5,7],2]

expected: -1

case 3

in: [[],1]

expected: -1

case 4

in: [[5],5]

expected: 0

case 5

in: [[5],4]

expected: -1

Starter codePython

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

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