Search Algorithms (Linear & Binary)

# CHAPTER 28

Search Algorithms (Linear & Binary) #

1. Introduction #

2. Learning Objectives #

• Write a basic Linear Search using iteration.

• Define the absolute physical prerequisite required to utilize Binary Search.

• Execute the mathematical mid-point calculations of Binary Search.

• Contrast O(n) Time Complexity vs O(log n) Time Complexity.

3. Linear Search (The Brute Force Approach) #

The Mechanics: Array: [14, 2, 7, 90, 5] Target: 90

• Is [0] == 90? No.

• Is [1] == 90? No.

• Is [2] == 90? No.

• Is [3] == 90? Yes! Return index 3.

// Java Example: Linear Search
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // Target found! Return the index instantly.
        }
    }
    return -1; // Loop finished without finding it. Return -1 (Error).
}

Complexity:

• Worst Case: O(n). If the array has 1 Million items, and the target is at the very end (or doesn't exist), the CPU must execute 1 Million checks.

4. Binary Search (The Logarithmic Powerhouse) #

#### The Absolute Prerequisite Binary Search CANNOT operate on randomized data. The array MUST BE PERFECTLY SORTED (e.g., using Merge Sort or Quick Sort) before you can run Binary Search!

The Mechanics: Sorted Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Target: 23

1. 1. Calculate Midpoint: The array has 10 elements. Midpoint is 16.

1. 2. Compare: Is 23 == 16? No.

1. 3. Eliminate: Is 23 > 16? YES! Because the array is sorted, 23 cannot possibly exist on the left side. We completely eliminate [2, 5, 8, 12, 16].

1. 4. Repeat: The remaining array is [23, 38, 56, 72, 91]. Find the new midpoint (56). Is 23 < 56? Yes. Eliminate the right side.

1. 5. Found: Midpoint is 23. Target acquired!

# Python Example: Binary Search (Iterative)
def binary_search(arr, target):
    left = 0              # Start pointer
    right = len(arr) - 1  # End pointer

    while left <= right:
        # Calculate the mathematical center index
        mid = (left + right) // 2 

        # Case 1: Target found at the center!
        if arr[mid] == target:
            return mid

        # Case 2: Target is LARGER. Discard the entire Left half.
        elif arr[mid] < target:
            left = mid + 1

        # Case 3: Target is SMALLER. Discard the entire Right half.
        else:
            right = mid - 1

    return -1 # Target absolutely does not exist.

5. Complexity Analysis (O(log n) vs O(n)) #

• If N = 100, Linear Search takes 100 steps. Binary Search takes 7 steps.

• If N = 1,000,000, Linear Search takes 1 Million steps. Binary Search takes 20 steps.

• If N = 4 Billion, Linear Search takes 4 Billion steps. Binary Search takes 32 steps.

Binary Search is explicitly O(log n) Time Complexity.

6. The Midpoint Calculation Bug (Advanced) #

*The Senior Developer Solution:* mid = left + ((right - left) / 2) This advanced mathematical formula achieves the exact same midpoint, but strictly avoids large addition, making it completely immune to Overflow crashes!

7. Real-World Applications #

1. 1. Database Queries: When you execute SELECT * FROM users WHERE id = 500, MySQL does not linearly scan the hard drive. It utilizes a B-Tree structure to execute Binary Search logic, retrieving the user in milliseconds.

1. 2. Git Bisect: If a developer introduced a bug 500 commits ago, git bisect uses Binary Search to jump to commit 250. If it's bug-free, it jumps to commit 375, finding the exact broken code in 9 steps!

8. Common Mistakes #

• Running Binary Search on Unsorted Data: If the array is [10, 2, 5], and you check the midpoint 2, the algorithm might assume the target 10 is on the right because 10 > 2. But 10 is actually on the left! The logarithmic routing logic shatters completely if the numbers are not perfectly sequential.

9. Exercises #

1. 1. Trace Binary Search looking for the number 7 in the sorted array [1, 3, 5, 7, 9, 11]. What are the values of left, right, and mid on the first iteration?

1. 2. If an array is completely chaotic and unsorted, is it faster to run Linear Search, or is it faster to sort the array with Merge Sort and then run Binary Search? *(Hint: Look at Time Complexities).*

10. MCQs with Answers #

11. Interview Preparation #

• *Algorithmic Coding:* "Given a sorted array that has been mysteriously rotated at a random pivot (e.g., [4, 5, 6, 7, 0, 1, 2]), write an O(log n) algorithm to find a target." *(Answer: The legendary LeetCode 'Search in Rotated Sorted Array'. You must use a heavily modified Binary Search to detect which half of the split array is normally sorted before shifting your boundary pointers!).*

12. FAQs #

13. Summary #

14. Next Chapter Recommendation #