Binary Search Techniques

# CHAPTER 9

Binary Search Techniques #

1. Chapter Introduction #

2. The Core Concept #

3. The Standard Binary Search Template #

*Prompt:* Find the index of target in a sorted array nums.

def binarySearch(nums, target):
    left = 0
    right = len(nums) - 1
    
    # 1. Condition: left <= right
    while left <= right:
        # 2. Calculate mid (prevent integer overflow)
        mid = left + (right - left) // 2 
        
        # 3. Check the middle
        if nums[mid] == target:
            return mid
        # 4. If target is larger, discard the left half
        elif nums[mid] < target:
            left = mid + 1
        # 5. If target is smaller, discard the right half
        else:
            right = mid - 1
            
    return -1 # Target not found
# Time: O(log N), Space: O(1)

4. Preventing Integer Overflow (The mid calculation) #

5. Pattern 1: Search Space Reduction (The Answer is NOT the exact target) #

public int firstBadVersion(int n) {
    int left = 1, right = n;
    int ans = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            ans = mid;       // Record the potential answer
            right = mid - 1; // Keep searching LEFT for an earlier one
        } else {
            left = mid + 1;  // Good version, search RIGHT
        }
    }
    return ans;
}

6. Pattern 2: Search in a Rotated Sorted Array #

1. 1. Find mid.

1. 2. Check if the Left side is perfectly sorted (is nums[left] <= nums[mid]).

• If Left is sorted: Is the target within this left range? If yes, discard Right. If no, discard Left.

1. 3. If Left is not sorted, the Right side MUST be perfectly sorted.

• Is the target within the right range? If yes, discard Left. If no, discard Right.

7. Real-World Scenario: Binary Search on the Answer Space #

• Min speed = 1 banana/hr.

• Max speed = Max pile size/hr.

• Binary search between 1 and Max. Check mid. Can she finish in time at speed mid? If yes, try a slower speed (discard right half). If no, try a faster speed (discard left half).

8. Mini Project: Find Minimum in Rotated Sorted Array #

• If nums[mid] > nums[right], we are in the high slope. The minimum MUST be to the right. left = mid + 1.

• If nums[mid] <= nums[right], we are in the low slope. The minimum is here or to the left. right = mid.

9. Common Mistakes #

• Infinite Loops (Off-by-One): The condition while left <= right is standard. However, if you update boundaries using left = mid and right = mid (instead of mid + 1 or mid - 1), the pointers can get stuck continuously checking the same middle element forever.

• Forgetting the Sorted Requirement: You cannot run Binary Search on an unsorted array. If you need to search, you must sort it first, which costs O(N log N) time, making the overall algorithm O(N log N).

10. Best Practices #

• Draw the Number Line: In an interview, draw a line. Plot L, M, and R. Erase L and move it past M. Visualizing the boundary shifts prevents index errors.

11. Exercises #

1. 1. Trace the standard Binary Search for target = 7 in [1, 3, 5, 7, 9]. What are the values of left, right, and mid at each step?

1. 2. Why is Binary Search exponentially faster than Linear Search?

12. MCQs #

14. Interview Questions #

• Q: "Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]." (LeetCode 34. Hint: Run Binary Search twice).

15. FAQs #

• Q: Does Python have a built-in Binary Search?

16. Summary #

17. Next Chapter Recommendation #