Binary Search Algorithm

# CHAPTER 10

Binary Search Algorithm #

1. Introduction #

2. Learning Objectives #

• Identify the absolute prerequisite condition for Binary Search.

• Calculate the mathematical midpoint using anti-overflow formulas.

• Trace the aggressive elimination logic iteratively.

• Implement Binary Search recursively and iteratively.

• Prove the catastrophic efficiency difference between $O(N)$ and $O(\log N)$.

3. The Absolute Law: Perfect Order #

4. The Execution Logic #

Algorithm Steps:

1. 1. Calculate the exact mid index between left and right.

1. 2. Evaluate array[mid]:

• Match: Target found! Return mid.

• Target is Larger: The target *must* be physically on the right side. We abandon the left. Update left = mid + 1.

• Target is Smaller: The target *must* be physically on the left side. We abandon the right. Update right = mid - 1.

1. 3. Repeat the loop until left mathematically crosses right (proving the search space is empty).

5. Implementation in Code (Iterative) #

// Java Example: Iterative Binary Search
public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    // Loop continues as long as the search boundary hasn't collapsed
    while (left <= right) {
        
        // Anti-Overflow Formula: Calculates precise geometric center
        int mid = left + (right - left) / 2;

        // 1. Target instantly acquired!
        if (arr[mid] == target) {
            return mid; 
        }

        // 2. Target is larger. Decimate the left hemisphere!
        if (arr[mid] < target) {
            left = mid + 1; 
        }
        
        // 3. Target is smaller. Decimate the right hemisphere!
        else {
            right = mid - 1; 
        }
    }
    
    // Boundary collapsed. Target does not exist.
    return -1; 
}

6. The Midpoint Overflow Bug #

7. Implementation in Code (Recursive) #

# Python Example: Recursive Binary Search
def recursive_binary_search(arr, left, right, target):
    # Base Case: The boundary has collapsed
    if right >= left:
        mid = left + (right - left) // 2

        # Hit
        if arr[mid] == target:
            return mid
            
        # Target is smaller: Recursively dive down the Left branch
        if arr[mid] > target:
            return recursive_binary_search(arr, left, mid - 1, target)
            
        # Target is larger: Recursively dive down the Right branch
        else:
            return recursive_binary_search(arr, mid + 1, right, target)

    return -1 # Not found

8. Complexity Analysis: $O(\log N)$ Logarithmic Power #

*By organizing our data beforehand, we reduced a 4-Billion step crawl into an instantaneous 32-step calculation!*

9. Real-World Applications #

1. 1. Database Indexes: When you set a column as UNIQUE or PRIMARY KEY in MySQL, the database builds a hidden B-Tree structure under the hood, natively executing Binary Search logic to fetch rows in milliseconds.

1. 2. Git Version Control: The command git bisect uses Binary Search traversing your historical code commits to find the exact commit that introduced a catastrophic bug, dramatically accelerating debugging.

10. Common Mistakes #

• The Infinite Loop Bug: Junior developers frequently write left = mid or right = mid instead of mid + 1 / mid - 1. If the target is not found, the mid pointer becomes completely frozen on the same number, and the while(left <= right) loop spins forever, crashing the browser. Always increment past the midpoint!

11. Exercises #

1. 1. Trace the explicit left, right, and mid values on each step of Binary Search finding 80 in the sorted array [10, 20, 30, 40, 50, 60, 70, 80].

1. 2. Why does the Recursive implementation of Binary Search have a worse Space Complexity than the Iterative implementation?

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Analysis:* "Given a sorted array containing duplicates (e.g., [1, 2, 2, 2, 5]), how do you modify Binary Search to explicitly find the *first* occurrence of 2?" *(Answer: When arr[mid] == target, do NOT return mid instantly! Save the index, and forcefully update right = mid - 1 to continuously crush the search space aggressively leftward until the bounds collapse!).*

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #