Deviopath › Python

Binary Search

Medium · Algorithms

Binary search finds a value in a sorted list by halving the search range each step: look at the middle item, then continue in the left or right half. It needs about 20 steps for a million items. The standard library has bisect.bisect_left, which finds where a value would be inserted.

Write binary_search(nums, target) that returns the index of target in nums (sorted ascending, no duplicates), or -1 if it is not there.

Next: Balanced Brackets