Binary search idea
- Algorithms course
- Beginner
- Lesson 53/80
- 4 min
Halve the range each step on a sorted array for O(log n).
Binary search logic
Binary search finds a target in a sorted array in O(log n) time. It halves the search space at each step.
It first checks the middle element. If the target equals it, it is found. If smaller, it searches the left half; if larger, the right half.
Sorted requirement
Binary search only works on sorted arrays. In an unsorted array, the middle element cannot tell which half to search.
Therefore you must sort the array before using binary search. Since sorting is O(n log n), for a single search linear search may be better.
Practice Binary search
Write binary_search(arr, target). Search with left-right pointers. Print 3 with print(binary_search([1, 3, 5, 7, 9], 7)).
Starter code
def binary_search(arr, target):
# Binary searchSample solution
def binary_search(arr, target):
# Binary search
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 On which array does binary search work?
- Only empty
- Only sorted Correct answer
- Only unsorted
- Any array
Explanation: It works only on sorted arrays.
2 Complexity
Binary search runs in ____ time.Binary search runs in O(log n) time.Explanation: O(log n) is right.
3 Binary search idea: match the terms
| Term | Meaning |
|---|---|
Binary search |
Sorted array |
O(log n) |
Speed |
Middle element |
Divide |
Sorted |
Requirement |