Binary search is one of the most efficient searching algorithms, but it only works on sorted data. Instead of checking every element like linear search, binary search uses a "divide and conquer" approach that eliminates half of the remaining possibilities with each comparison.
The key insight is this: if you're looking for a number in a sorted list, you can check the middle element first. If your target is smaller than the middle element, you know it must be in the left half (if it exists at all). If your target is larger, it must be in the right half. This allows you to throw away half the data with just one comparison!
The algorithm works with two pointers that define the current search boundaries: left and right. Initially, left starts at index 0 and right starts at the last index. In each iteration, you calculate the middle index and compare the middle element with your target. Based on the comparison, you adjust either the left or right boundary to focus on the half that could contain your target.
This process continues until either you find the target (success!) or the search space becomes empty (the target doesn't exist in the array). You know the search space is empty when left becomes greater than right.
The beauty of binary search is its efficiency. While linear search might need to check every single element in the worst case, binary search cuts the problem size in half with each step. For an array of 1,000 elements, binary search needs at most 10 comparisons to find any element or determine it's not there. For a million elements, it needs at most 20 comparisons!
1# Simple example of the binary search concept
2def find_number_in_range(target, low, high):
3 """Demonstrates the halving concept of binary search"""
4 attempts = 0
5
6 while low <= high:
7 attempts += 1
8 mid = (low + high) // 2
9 print(f"Attempt {attempts}: Checking {mid}")
10
11 if mid == target:
12 return f"Found {target} in {attempts} attempts!"
13 elif mid < target:
14 low = mid + 1 # Search upper half
15 else:
16 high = mid - 1 # Search lower half
17
18 return f"Not found after {attempts} attempts"
19
20# Example: Find 47 between 1 and 100
21result = find_number_in_range(47, 1, 100)