Summary - Binary search
- Algorithms course
- Beginner
- Lesson 56/80
- 4 min
Implement binary search and print the result.
Summary - Binary search
In this group you learned binary search's logic, left-right pointers, base case and recursive version. Complexity is O(log n).
Binary search is the fastest search method on sorted arrays. The search space halves at each step.
Practice Binary search (simple)
Write binary_simple(arr, target). Search with while. Print 2 with print(binary_simple([10, 20, 30, 40, 50], 30)).
Starter code
def binary_simple(arr, target):
# Simple binary searchSample solution
def binary_simple(arr, target):
# Simple binary search
lo = 0
hi = len(arr) - 1
while lo <= hi:
m = (lo + hi) // 2
if arr[m] == target:
return m
if arr[m] < target:
lo = m + 1
else:
hi = m - 1
return -1
print(binary_simple([10, 20, 30, 40, 50], 30))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Binary search: match the terms
| Term | Meaning |
|---|---|
Binary search |
Sorted array |
O(log n) |
Speed |
mid |
Middle |
left <= right |
Loop |
2 Binary search
Question
Binary search ____ the search space each step.
Answer
Binary search halves the search space each step.Explanation: halves is right.
3 Why is binary search fast?
- Visits every element
- Sorts the array
- Halves the search space Correct answer
- Uses hash
Explanation: It halves the search space.