Binary search
Searching a sorted array by halving the interval: left and right bounds, middle, the half kept, stopping condition, bound updates and the maximum number of steps.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Binary search: what is it?
Show the answer
An algorithm that compares the sought value with the middle item of a sorted array, then keeps only the half where it can be.
Each comparison halves the interval: a million cells are settled in about twenty steps, where a linear search needs up to a million.
What does this program print?
```python
def binary_search(t, v):
g, d = 0, len(t) - 1
while g <= d:
m = (g + d) // 2
if t[m] == v:
return m
elif t[m] < v:
g = m + 1
else:
d = m - 1
return -1
t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(t, 23))`546-1
Show the answer
5First middle: m = 4,
t[4]is 16, smaller than 23, so g = 5. Second middle: m = 7, 56 is too big, so d = 6. Third middle: m = 5,t[5]is 23, found in three comparisons.The middle of the interval is computed with
m = (g + d) // 2, and whent[m] < vwe carry on to the right with ….Show the answer
The middle of the interval is computed with
m = (g + d) // 2, and whent[m] < vwe carry on to the right with g = m + 1.Cell
mhas just been compared and does not match: it must leave the interval. Without the+ 1, the same cell comes back on every pass.Sorted precondition: what is it?
Show the answer
A condition that must hold before the search is called: the items are already arranged in increasing order.
If it is false, the function reports no error: it simply answers wrongly, for instance “absent” for a value that is in fact present.