I. In-Class Exercises

Programming Exercises

1. Binary Search: Find the index of a specific number in a non-duplicate array: L3131
2. Binary Search: For an array with possible duplicates, find the smallest index equal to a given number: L3132
3. Binary Search: Find the largest index less than or equal to a given number: L3133

II. Knowledge Summary

✨ Core Idea

Binary Search is an efficient search algorithm used to find a specific element in a sorted array. It achieves low time complexity by progressively narrowing the search range, making it one of the most fundamental and important algorithms.

Key characteristics of binary search:

• Prerequisite: Binary search can only be used on sorted arrays or lists
• How it works: By comparing the target value with the middle element, it decides which half of the array to continue searching in, progressively narrowing the range until the target is found or the range is empty
• High efficiency: Compared to linear search, binary search is much faster, especially when dealing with large datasets
• Limitation: The array must be sorted. If the data is unsorted, it needs to be sorted first, which may add extra time overhead

✨ Algorithm Principle

The specific execution steps of binary search are as follows:

1. Initialize boundaries: Set two pointers, left and right, pointing to the start and end positions of the array respectively.
2. Calculate the midpoint: Compute the midpoint index mid, typically using the formula mid = left + (right - left) / 2 to avoid potential integer overflow.
3. Compare the midpoint value:
   • If a[mid] equals the target value target, return the midpoint index
   • If a[mid] is less than target, update left to mid + 1 and continue searching in the right half
   • If a[mid] is greater than target, update right to mid - 1 and continue searching in the left half
4. Loop termination: When left exceeds right, the target value was not found.

✨ Algorithm Evaluation

• Time Complexity: O(log n). Each operation halves the search range, so even with millions of data points, only about 20 comparisons are needed to complete the search.
• Space Complexity: O(1). Only constant extra space is used (iterative implementation).

✨ Application Scenarios

Binary search is suitable for the following scenarios:

• Finding a specific value in sorted data
• Solving problems with monotonicity (such as minimization and maximization problems)
• Implementing efficient dynamic data structures (such as operations in balanced binary search trees)

✨ Code Implementation

Here is the standard binary search code implementation that searches for a target value in a sorted array and returns its index:

1#include <iostream>
2#include <vector>
3using namespace std;
4
5int binarySearch(const vector<int>& nums, int target) {
6    int left = 0;
7    int right = nums.size() - 1;
8
9    while (left <= right) {
10        int mid = left + (right - left) / 2;
11
12        if (nums[mid] == target) {
13            return mid; // Target found, return index
14        } else if (nums[mid] < target) {
15            left = mid + 1; // Target is in the right half
16        } else {
17            right = mid - 1; // Target is in the left half
18        }
19    }
20
21    return -1; // Target not found, return -1
22}
23
24int main() {
25    vector<int> nums = {1, 3, 5, 7, 9, 11};
26    int target = 7;
27
28    int result = binarySearch(nums, target);
29    if (result != -1) {
30        cout << "Element found at index " << result << endl;
31    } else {
32        cout << "Element not found" << endl;
33    }
34
35    return 0;
36}

✨ Execution Example

Using the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] to search for target=23 as an example:

Only 3 comparisons were needed to find the target, while linear search would require 6.

Now let's look at an example of searching for a non-existent element: searching for target=20 in the same array:

After 4 comparisons, it is determined that the element does not exist.

✨ Detailed Problem-Solving Steps

When encountering binary search problems, pay special attention to the differences between variants:

1. Standard binary search (finding an exact value): Return the index when found, return -1 when not found. Loop condition is left <= right, return immediately when found.
2. Finding the first position equal to target: After finding nums[mid] == target, you cannot return immediately. Instead, record the answer and continue searching in the left half (right = mid - 1).
3. Finding the last position equal to target: After finding it, record the answer and continue searching in the right half (left = mid + 1).
4. Finding the first position greater than or equal to target: When nums[mid] >= target, record the answer and search the left half.
5. Finding the last position less than or equal to target: When nums[mid] <= target, record the answer and search the right half.

Mastering these variants is the key to binary search. It is recommended to understand and practice each one individually.

✨ Common Mistakes

• Using binary search on an unsorted array: Binary search requires the array to be sorted. If the data is unsorted, it must be sorted first.
• Mid calculation overflow: (left + right) / 2 may overflow when both left and right are very large. Use left + (right - left) / 2 instead.
• Incorrect boundary updates: left = mid or right = mid may cause infinite loops (when left + 1 == right, mid always equals left). The correct approach is usually left = mid + 1 or right = mid - 1.
• Confusing loop conditions: left <= right and left < right correspond to different binary search implementations and cannot be mixed. With <=, exiting the loop means left > right; with <, exiting the loop means left == right.
• Forgetting to record the answer in variant implementations: In variants for finding the "first" or "last" position, you cannot return directly when a match is found. You need to record the current position first and then continue narrowing the range.

III. Homework

Programming Exercises

1. Binary Search: Find the smallest index greater than or equal to a given number: L3134
2. Binary Search: Find the largest index less than a given number: L3135
3. Binary Search: Find the smallest index greater than a given number: L3136
4. Binary Search: Find the largest index equal to a given number: L3137