In our daily study and life, we often encounter scenarios of “finding something”. For example, looking up a word in a dictionary, finding a phone number in a directory, or searching for the price of a product in a list. These “finding” processes correspond to search algorithms in computers. There are many types of search algorithms, and today we’ll start with the simplest linear search, gradually move on to the more efficient binary search, and see what makes it so fast.
一、What is Linear Search?¶
Linear search (also known as sequential search) is the most basic search method. Its principle is very simple: Check each element one by one from start to end until the target element is found.
For example: Suppose we have an array [2, 5, 8, 12, 16] and we want to find the number 8.
- Step 1: Check the first element
2—not the target; - Step 2: Check the second element
5—not the target; - Step 3: Check the third element
8—found!
If the target element does not exist, linear search will traverse the entire array before ending.
Characteristics of Linear Search:¶
- Time Complexity:
- Best case: The target is at the first position, requiring only 1 check (denoted as O(1));
- Worst case: The target is at the last position or does not exist, requiring traversal of the entire array (denoted as O(n), where n is the data size);
- Average case: Still O(n), as on average half the data needs to be checked.
For example, when the data size is 10,000, linear search could require up to 10,000 checks in the worst case, making it very inefficient for large datasets.
二、Binary Search: From “One-by-One” to “Half Elimination”¶
The downside of linear search is its low efficiency, especially with large datasets. Is there a faster method? Yes, that’s Binary Search.
Prerequisite for Binary Search:¶
Binary search can only be used on sorted arrays (e.g., arrays sorted in ascending or descending order). If the array is unsorted, binary search is not applicable.
Principle of Binary Search:¶
Its core idea is “Eliminate half the data each time”. Here’s how it works:
1. First, find the middle position of the array and compare the middle element with the target;
2. If the middle element equals the target, the target is found;
3. If the middle element is larger than the target, the target must be in the left half—continue searching there;
4. If the middle element is smaller than the target, the target must be in the right half—continue searching there;
5. Repeat until the target is found or confirmed to be non-existent.
Understanding Binary Search with Examples:¶
Using the same sorted array [2, 5, 8, 12, 16] to find 8:
- First search: The array length is 5, so the middle position is the 2nd element (index 2, value 8). It matches the target, so found immediately!
Another example: Find 12:
- First search: Middle element is
8(index 2). Since8 < 12, the target is in the right half: remaining array[12, 16]; - Second search: New array length is 2, middle position is the 1st element (value 12). Matches the target, found!
Time Complexity of Binary Search:¶
Each search eliminates half the data, so the number of checks is related to the “logarithm” of the data size. The time complexity is O(log n) (log here is base-2 logarithm).
For example:
- When n=1000, log₂(1000) ≈ 10 (up to 10 checks);
- When n=10,000, log₂(10000) ≈ 14 (up to 14 checks);
- When n=1,000,000, log₂(1000000) ≈ 20 (up to 20 checks).
三、How Much Faster is Binary Search Than Linear Search?¶
Let’s compare with specific data:
| Data Size n | Linear Search (Worst Case) | Binary Search (Worst Case) | Speed Difference |
|---|---|---|---|
| 100 | 100 checks | 7 checks (log₂100≈7) | ~14x faster |
| 1000 | 1000 checks | 10 checks (log₂1000≈10) | ~100x faster |
| 10000 | 10000 checks | 14 checks (log₂10000≈14) | ~700x faster |
| 1000000 | 1,000,000 checks | 20 checks (log₂1e6≈20) | ~50,000x faster |
Key Conclusion: The larger the data size n, the more significant the speed advantage of binary search. For example, with n=1,000,000, binary search takes only 20 checks, while linear search requires 1,000,000 checks—a 50,000x difference!
四、When to Use Binary Search vs. Linear Search?¶
Applicable Scenarios for Binary Search:¶
- Data is sorted (e.g., pre-sorted lists/arrays);
- Data size is large (efficiency advantage is more pronounced);
- Frequent searches are needed (binary search’s “setup time” is for sorting, but fixed sorted arrays make subsequent searches very efficient).
Applicable Scenarios for Linear Search:¶
- Data is unsorted (binary search is not applicable);
- Data size is very small (e.g., only a few elements—linear search is simpler and requires no extra preparation);
- Data is dynamically changing (frequent insertions/deletions disrupt order, making linear search more flexible).
五、Summary: The Core Value of Binary Search¶
Binary search is a classic “high-efficiency search technique” in data structures. By using the “half-elimination” strategy, it reduces the number of checks from O(n) to O(log n), making it far more efficient than linear search for large datasets. Remember: A sorted array is the prerequisite for binary search. If data is unsorted, linear search is the only option.
For beginners, understanding binary search’s “half-elimination” logic, mastering its time complexity analysis, and comparing it with linear search will help choose the right search method based on data characteristics. As data size grows, binary search’s advantages become increasingly prominent, which is why it’s a frequent topic in algorithm interviews and real-world development.