Binary Search: The Efficient Search Algorithm for Beginners¶

Have you ever played the “Guess the Number” game? For example, thinking of a number between 1 and 100, and someone guesses a number, and you just say “too big” or “too small”—they can quickly guess it. This process is actually the idea of binary search—each time narrowing down the range by half using the middle value to quickly locate the target.

What is Binary Search?¶

Binary Search (also called half-interval search) is an algorithm that quickly locates a target element in a sorted array. Its core idea is: by continuously comparing the middle element, the search range is “halved” until the target is found or determined to not exist.

Why do we need a sorted array?¶

Suppose the array is unsorted, like [3, 1, 4, 2, 5]. If someone guesses the middle number is 4, they can’t determine if the target is on the left or right (e.g., if the target is 1, 4 is larger than 1, but there are still 3 and 1 on the left that need to be compared). Only when the array is sorted can the middle element act as a “dividing point,” and the target can be directly determined to be on which side by comparing sizes.

Applicable Scenarios for Binary Search¶

Binary search is efficient but has clear application conditions and isn’t suitable for all scenarios:

1. Data must be sorted (ascending or descending order, ascending is most common).
2. Large data volume: When the data volume n is large (e.g., 10,000 elements), binary search is much more efficient than linear search (comparing one by one).
3. Static data: If data is frequently inserted, deleted, or modified, the cost of maintaining a sorted array is high, and the advantages of binary search will be offset.
4. Need for quick search: Suitable for scenarios of “once built, multiple queries” (e.g., dictionaries, configuration files).

Search Process Example¶

Take the array [1, 3, 5, 7, 9, 11, 13] as an example, and the target is to find 7:

1. Initial range: Left pointer left=0 (points to 1), right pointer right=6 (points to 13).
2. First middle value: mid = (0+6)//2 = 3 (the element at index 3 is 7? Wait, the array is [1(0), 3(1), 5(2), 7(3), 9(4), 11(5), 13(6)], so mid=3 is exactly 7! Found directly, return index 3.

Another example finding 9:
- Initial left=0, right=6, mid=3 (element 7).
- Since 9 > 7, the target is in the right half, so left = mid + 1 = 4.
- New range: left=4, right=6, mid=(4+6)//2=5 (element 11).
- Since 9 < 11, the target is in the left half, so right = mid - 1 = 4.
- New range: left=4, right=4, mid=4 (element 9), target found, return index 4.

Code Implementation (Iterative Method)¶

Here’s a basic binary search function implemented in Python, suitable for beginners to reference directly:

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1  # Initial right pointer points to the last element
    while left <= right:  # Valid range: left pointer <= right pointer
        mid = (left + right) // 2  # Calculate middle position (integer division)
        if nums[mid] == target:
            return mid  # Target found, return index
        elif nums[mid] < target:
            left = mid + 1  # Target is in the right half, move left pointer right
        else:
            right = mid - 1  # Target is in the left half, move right pointer left
    return -1  # Not found after traversal, return -1

Key Detail Explanations:¶

• Loop Condition: left <= right ensures that when the range is reduced to one element (left=right), the element is still checked for being the target.
• Middle Value Calculation: mid = (left + right) // 2 uses integer division in Python to automatically round down, ensuring the range is correctly narrowed.
• Boundary Handling: If the array is empty (len(nums)=0), return -1 directly. If the target does not exist, return -1 when left > right.

Time and Space Complexity¶

• Time Complexity: Each search halves the range, with the number of operations being log₂n (where n is the array length), so O(log n). For example, when n=10000, at most 14 searches are needed (2¹⁴=16384).
• Space Complexity: The iterative implementation only uses three variables: left, right, and mid, so it is O(1) (constant level).

Common Questions and Solutions¶

1. What if there are duplicate elements in the array?
   The basic binary search may return the position of any duplicate element. If all duplicates need to be found, after finding a target, expand left and right to traverse.

2. How to handle when the array length is 1?
   Directly enter the loop for judgment: left=0, right=0, mid=0, compare and return or exit.

3. Return -1 when the target is not found:
   Clearly inform the user that the target is not found to avoid returning random values.

Summary¶

The core of binary search is “Divide and Conquer”—by comparing the middle value each time, the search range is quickly narrowed down. Remember these key points:
- Prerequisite: The array must be sorted.
- Advantages: Extremely efficient for large datasets (O(log n)) with minimal space usage (O(1)).
- Scenarios: Fast searches for static, sorted data (e.g., dictionaries, configuration tables).

As long as you understand the logic of “middle value comparison + range adjustment,” binary search is actually easy to master. Try writing the iterative version of binary search yourself to solve problems like “finding a specific number in a sorted array”!