Binary Search Algorithm

Binary search is an efficient algorithm for finding a specific element in a sorted array. Its core idea is to quickly locate the target value by repeatedly halving the search interval. Below, I will explain in detail the principle, steps, boundary handling, and code implementation of binary search.

1. Basic Idea and Applicable Conditions

• Core Idea: Utilize the sorted nature of the array, comparing the target value with the middle element of the interval each time, thereby reducing the search scope by half.
• Prerequisites:
  1. The array must be sorted (ascending or descending).
  2. The array supports random access (i.e., direct element access via indices).
• Time Complexity: O(log n), which is far superior to the O(n) of linear search.

2. Detailed Algorithm Steps (Using Ascending Array as an Example)

Assume searching for a target value target in the sorted array arr, with the initial search interval being the entire array:

1. Initialize Pointers:

   • Left boundary left = 0 (points to the first element)
   • Right boundary right = n-1 (points to the last element, where n is the array length)

2. Loop Condition:

   • When left <= right, the interval is valid, continue searching. If left > right, the target does not exist.

3. Calculate Middle Position:

   • Take the middle index mid = left + (right - left) // 2.
     (Using this formula instead of (left + right) // 2 prevents integer overflow)

4. Compare and Adjust Boundaries:

   • If arr[mid] == target: Target found, return mid.
   • If arr[mid] < target: Target is on the right side, adjust left boundary left = mid + 1.
   • If arr[mid] > target: Target is on the left side, adjust right boundary right = mid - 1.

5. Termination Condition:

   • Return the index directly when the target is found.
   • If the loop ends without finding the target, return -1 to indicate the target does not exist.

3. Key Details and Boundary Handling

• Why left <= right?
  If the interval is [left, right] (closed interval), when left == right the interval still contains one element, which needs further checking. If changed to left < right, the single-element case would be missed.

• Why adjust boundaries with mid ± 1?
  Because arr[mid] has already been confirmed not to be the target, the next step should directly exclude the mid position and search its left or right interval to avoid repeated checks.

• Preventing Integer Overflow:
  Use left + (right - left) // 2 instead of (left + right) // 2 when calculating mid to ensure no overflow occurs when left and right are very large.

4. Code Implementation (Python Example)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # Initialize closed interval [left, right]
    
    while left <= right:
        mid = left + (right - left) // 2  # Prevent overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # Target is on the right, narrow to [mid+1, right]
        else:
            right = mid - 1  # Target is on the left, narrow to [left, mid-1]
    
    return -1  # Not found

5. Examples of Variant Problems

Binary search has several variants, for example:

• Find the first element equal to the target: When arr[mid] == target, do not return immediately but continue shrinking the left boundary (right = mid - 1).
• Find the last element equal to the target: Similarly, shrink the right boundary (left = mid + 1).
• Find the first element greater than or equal to the target: Adjust boundaries by combining comparison conditions.

These variants require fine-tuning the loop conditions and boundary operations based on the specific problem, but the core idea remains "halving step by step".