DSA Binary Search
Binary search is an efficient algorithm for finding a value in a sorted sequence by repeatedly halving the range that could contain it.
What Is Binary Search?
Binary search locates a target value inside a sorted array by comparing it to the middle element and discarding the half of the array that cannot contain the target. Because each comparison eliminates roughly half of the remaining candidates, the search space shrinks exponentially instead of linearly, which is what makes the algorithm so much faster than scanning every element.
Why the Input Must Be Sorted
The halving trick only works because a sorted array guarantees that everything to the left of an element is smaller (or equal) and everything to the right is larger (or equal). If the array were unsorted, discarding a half based on one comparison could throw away the very element you were looking for, so binary search would silently give incorrect results on unsorted input.
- Set low to the first index and high to the last index of the array.
- Compute mid as the midpoint between low and high.
- If the value at mid equals the target, return mid.
- If the target is smaller than the value at mid, search the left half by setting high = mid - 1.
- If the target is larger, search the right half by setting low = mid + 1.
- Repeat until low exceeds high, at which point the target is not present.
Example
def binary_search(sorted_list, target):
low = 0
high = len(sorted_list) - 1
while low <= high:
mid = low + (high - low) // 2
if sorted_list[mid] == target:
return mid
elif sorted_list[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
print(binary_search(numbers, 23)) # 5
print(binary_search(numbers, 100)) # -1Example
def binary_search_recursive(sorted_list, target, low=0, high=None):
if high is None:
high = len(sorted_list) - 1
if low > high:
return -1
mid = low + (high - low) // 2
if sorted_list[mid] == target:
return mid
elif sorted_list[mid] < target:
return binary_search_recursive(sorted_list, target, mid + 1, high)
else:
return binary_search_recursive(sorted_list, target, low, mid - 1)
letters = ["a", "c", "e", "g", "i", "k", "m"]
print(binary_search_recursive(letters, "i")) # 4
print(binary_search_recursive(letters, "z")) # -1Time Complexity
Example
import bisect
numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
index = bisect.bisect_left(numbers, 23)
if index < len(numbers) and numbers[index] == 23:
print(f"Found 23 at index {index}")
else:
print("23 is not in the list")
# bisect_left also tells you where to insert a new value
# while keeping the list sorted.
insert_at = bisect.bisect_left(numbers, 20)
print(f"Insert 20 at index {insert_at} to keep the list sorted")Exercise: DSA Binary Search
What is a precondition for binary search to work correctly?
