Binary search finds a value in a sorted array by repeatedly cutting the search space in half. Each step you look at the middle element and ask one question: is the target bigger or smaller? The answer lets you discard half the remaining elements at once, which is why even a million-element array is found in about twenty steps.
Example: Find 23 in a sorted array of 10 numbers.
When to use this
→Search a sorted array for a target value in O(log n)
→Find the first/last occurrence of a value in a sorted array
→Find the insertion position for a value (lower_bound / upper_bound)
→Binary search on the answer space — e.g. 'minimum feasible capacity' problems
We start by looking at the whole array. Because it is sorted, we never have to scan every element. Two markers, lo and hi, fence off the part we still care about.
Space play/pause← → stepR replay+ − speed
active line highlighted
1
defbinary_search(arr,target):
2
lo,hi=0,len(arr)-1
3
whilelo<=hi:
4
mid=(lo+hi)//2
5
ifarr[mid]==target:
6
returnmid
7
elifarr[mid]<target:
8
lo=mid+1
9
else:
10
hi=mid-1
11
return-1
Quick check
Why does binary search require the array to be sorted?
Roughly how many steps does binary search take on an array of 1,000,000 elements?