binary_search()

Search for a target value in a sorted list.

Usage

binary_search(
    arr,
    target,
)

Uses the binary search algorithm to find the index of target in the sorted list arr. Returns -1 if the target is not found.

Parameters

arr: list

A sorted list of integers to search.

target: int

The integer value to search for.

Returns

int

The index of target in arr, or -1 if not found.

Notes

The input list must be sorted in ascending order. If the list is not sorted, the result is undefined.

The time complexity is O(log n) and the space complexity is O(1).

References

1. Knuth, D.E. (1998). “The Art of Computer Programming”, Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, Section 6.2.1.

Examples

>>> binary_search([1, 3, 5, 7, 9], 5)
2

>>> binary_search([1, 3, 5, 7, 9], 4)
-1