Binary Search
Master the efficient divide-and-conquer search algorithm
🎯 What is Binary Search?
Binary Search is an efficient algorithm for finding an item from a sorted list by repeatedly dividing the search interval in half. It compares the target value to the middle element and eliminates half of the remaining elements.
def binary_search(arr, target):
left, right = 0, 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 # Not found
O(log n)
Time Complexity
O(1)
Space Complexity
Sorted
Requirement
Binary Search Characteristics
Efficient
O(log n) time complexity
Fast searches
Logarithmic time
Divide & Conquer
Eliminates half each iteration
Recursive approach
Problem reduction
Requires Sorted Data
Only works on sorted arrays
Preprocessing needed
Order dependency
Precise
Exact match or insertion point
Find exact value
Find position
Lesson 1: Basic Binary Search Implementation
Let's implement binary search step by step:
Binary Search Visualization
Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Target: 7
Step 1: left=0, right=9, mid=4 → arr[4]=9 > 7
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
^ ^ ^
left mid right (new)
Step 2: left=0, right=3, mid=1 → arr[1]=3 < 7
[1, 3, 5, 7]
^ ^ ^
left mid right (new)
Step 3: left=2, right=3, mid=2 → arr[2]=5 < 7
[5, 7]
^ ^
left mid/right (new)
Step 4: left=3, right=3, mid=3 → arr[3]=7 = 7 ✅
[7]
^
left/mid/right
Iterative Binary Search
def binary_search(arr, target):
"""
Binary search implementation (iterative)
Returns index if found, -1 if not found
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # Search right half
else:
right = mid - 1 # Search left half
return -1 # Not found
def binary_search_with_steps(arr, target):
"""Binary search with step visualization"""
print(f"Searching for {target} in {arr}")
left, right = 0, len(arr) - 1
step = 1
while left <= right:
mid = (left + right) // 2
print(f"Step {step}: left={left}, right={right}, mid={mid}")
print(f" arr[{mid}] = {arr[mid]}")
if arr[mid] == target:
print(f"✅ Found {target} at index {mid}")
return mid
elif arr[mid] < target:
print(f" {arr[mid]} < {target}, search right half")
left = mid + 1
else:
print(f" {arr[mid]} > {target}, search left half")
right = mid - 1
step += 1
print(f"❌ {target} not found")
return -1
# Test binary search
sorted_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7
print("=== Basic Binary Search ===")
result = binary_search(sorted_array, target)
print(f"Result: {result}")
print("\n=== Step-by-step Binary Search ===")
result = binary_search_with_steps(sorted_array, target)
Lesson 2: Recursive Binary Search
Binary search can also be implemented recursively:
Recursive Binary Search
def binary_search_recursive(arr, target, left=0, right=None):
"""
Recursive binary search implementation
"""
if right is None:
right = len(arr) - 1
# Base case: element not found
if left > right:
return -1
mid = (left + right) // 2
# Base case: element found
if arr[mid] == target:
return mid
# Recursive cases
if arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
def binary_search_recursive_with_trace(arr, target, left=0, right=None, depth=0):
"""Recursive binary search with call trace"""
if right is None:
right = len(arr) - 1
indent = " " * depth
print(f"{indent}Call: left={left}, right={right}")
if left > right:
print(f"{indent}Base case: not found")
return -1
mid = (left + right) // 2
print(f"{indent}mid={mid}, arr[{mid}]={arr[mid]}")
if arr[mid] == target:
print(f"{indent}Base case: found at {mid}")
return mid
if arr[mid] < target:
print(f"{indent}Recursive call: search right half")
return binary_search_recursive_with_trace(arr, target, mid + 1, right, depth + 1)
else:
print(f"{indent}Recursive call: search left half")
return binary_search_recursive_with_trace(arr, target, left, mid - 1, depth + 1)
# Test recursive binary search
print("=== Recursive Binary Search ===")
result = binary_search_recursive(sorted_array, 13)
print(f"Result: {result}")
print("\n=== Recursive Binary Search with Trace ===")
result = binary_search_recursive_with_trace(sorted_array, 13)
Lesson 3: Binary Search Variations
Different variations for specific use cases:
Binary Search Variations
def find_first_occurrence(arr, target):
"""Find the first occurrence of target in sorted array with duplicates"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1 # Continue searching left for first occurrence
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
def find_last_occurrence(arr, target):
"""Find the last occurrence of target in sorted array with duplicates"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
left = mid + 1 # Continue searching right for last occurrence
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
def find_insertion_point(arr, target):
"""Find the index where target should be inserted to maintain sorted order"""
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
def search_range(arr, target):
"""Find the range [first, last] of target in sorted array"""
first = find_first_occurrence(arr, target)
if first == -1:
return [-1, -1]
last = find_last_occurrence(arr, target)
return [first, last]
# Test variations
test_array = [1, 2, 2, 2, 3, 4, 4, 5, 6, 7]
target = 2
print("Array:", test_array)
print(f"First occurrence of {target}: {find_first_occurrence(test_array, target)}")
print(f"Last occurrence of {target}: {find_last_occurrence(test_array, target)}")
print(f"Range of {target}: {search_range(test_array, target)}")
print(f"Insertion point for 2.5: {find_insertion_point(test_array, 2.5)}")
Lesson 4: Binary Search Applications
Real-world applications of binary search:
Binary Search Applications
import math
def find_square_root(n, precision=6):
"""Find square root using binary search"""
if n < 0:
return None
if n == 0 or n == 1:
return n
left, right = 0, n
while right - left > 10**(-precision):
mid = (left + right) / 2
square = mid * mid
if square == n:
return mid
elif square < n:
left = mid
else:
right = mid
return (left + right) / 2
def search_in_rotated_array(arr, target):
"""Binary search in rotated sorted array"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
# Check which half is sorted
if arr[left] <= arr[mid]: # Left half is sorted
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else: # Right half is sorted
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
def find_peak_element(arr):
"""Find a peak element (greater than neighbors)"""
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] < arr[mid + 1]:
left = mid + 1
else:
right = mid
return left
def search_2d_matrix(matrix, target):
"""Binary search in sorted 2D matrix"""
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
mid_value = matrix[mid // cols][mid % cols]
if mid_value == target:
return True
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return False
# Test applications
print("=== Square Root using Binary Search ===")
print(f"√25 = {find_square_root(25)}")
print(f"√10 = {find_square_root(10):.6f}")
print("\n=== Search in Rotated Array ===")
rotated = [4, 5, 6, 7, 0, 1, 2]
print(f"Search 0 in {rotated}: {search_in_rotated_array(rotated, 0)}")
print("\n=== Find Peak Element ===")
peak_arr = [1, 2, 3, 1]
print(f"Peak in {peak_arr}: index {find_peak_element(peak_arr)}")
print("\n=== Search in 2D Matrix ===")
matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16]]
print(f"Search 5 in matrix: {search_2d_matrix(matrix, 5)}")
Binary Search vs Linear Search
Time Complexity
- Binary: O(log n)
- Linear: O(n)
- Difference: Exponential improvement
- Example: 1M elements: 20 vs 500K steps
Requirements
- Binary: Sorted data required
- Linear: Works on any data
- Preprocessing: Sorting cost O(n log n)
- Trade-off: Sort once, search many
Use Cases
- Binary: Large datasets, frequent searches
- Linear: Small datasets, one-time searches
- Memory: Both O(1) space
- Implementation: Binary more complex
Performance Comparison
- 100 elements: 7 vs 50 steps
- 1K elements: 10 vs 500 steps
- 1M elements: 20 vs 500K steps
- 1B elements: 30 vs 500M steps