In programming or daily life, we often need to find a specific element from a pile of data, such as looking up a friend’s phone number in an address book or a classmate’s score in a report card. This process of “locating the target element” is exactly what search algorithms aim to solve. Today, we’ll discuss two of the most basic search algorithms: Sequential Search and Binary Search, and explore their differences and which one is faster.
1. What is a Search?¶
Imagine searching for a name in a phone book without a table of contents—you have to flip through each page one by one. Or looking for a specific student’s score in a stack of unordered exam papers—you have to check each paper individually. This “checking one by one” is the core idea of searching. However, more efficient search methods require smarter strategies.
2. Sequential Search: The Simplest “Check One by One”¶
1. Principle¶
Sequential Search (also called Linear Search) is the most straightforward method: start from the first element of the data, compare each element with the target one by one, until the target is found or all elements are checked.
2. Example (Using an Array)¶
Suppose we have an array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] and we want to find the number 16:
- 1st element: 2 ≠ 16 → Continue;
- 2nd element: 5 ≠ 16 → Continue;
- 3rd element: 8 ≠ 16 → Continue;
- 4th element: 12 ≠ 16 → Continue;
- 5th element: 16 = 16 → Found!
3. Pros and Cons¶
- Pros: Simple, no need for data to be sorted, works for any scenario.
- Cons: Low efficiency. In the worst case (e.g., 10,000 elements), it checks all elements, with a time complexity of O(n) (where n is the data size).
3. Binary Search: “Halving” for Efficient Search¶
1. Principle¶
Binary Search (also called Half-Interval Search) requires the data to be sorted (e.g., in ascending order). Its core is “halving comparison”: first find the middle element. If the middle element equals the target, the target is found. If the middle element is larger than the target, the target must be on the left; if smaller, the target is on the right. Repeat this process, narrowing the search range by half each time.
2. Example (Using an Ordered Array)¶
Using the same array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] to find 16:
- Step 1: The array range is [0,9] (indices 0 to 9). The middle position is (0+9)//2 = 4 (the 5th element), and the middle element is 16 → Found immediately!
If looking for 23:
- Step 1: Range [0,9], middle element is 16 (index 4). Since 23 > 16, the target is on the right, new range [5,9];
- Step 2: Middle position (5+9)//2 = 7 (the 8th element), middle element is 56. Since 23 < 56, the target is on the left, new range [5,6];
- Step 3: Middle position (5+6)//2 = 5 (the 6th element), middle element is 23 → Found!
3. Pros and Cons¶
- Pros: Extremely efficient, with a time complexity of O(log n) (e.g., for n=1000, log₂1000 ≈ 10 steps, 100 times faster than sequential search).
- Cons: Requires an ordered array; if data is unsorted, it cannot be used. Boundary conditions must be handled carefully (e.g., middle position calculation, range adjustment).
4. Sequential Search vs. Binary Search: Comparison Summary¶
| Comparison Item | Sequential Search | Binary Search |
|---|---|---|
| Prerequisite | No need for sorted data | Must be an ordered array |
| Search Method | Compare one by one from left to right | Halving search, narrowing the range by half each time |
| Time Complexity | O(n) (n = data size) | O(log n) |
| Implementation | Simple, no boundary issues | Requires handling boundary conditions (e.g., middle position) |
| Use Cases | Small data size, unordered; frequent additions/deletions | Large data size, ordered; static data scenarios |
5. Which is Faster?¶
Binary Search is faster! The efficiency advantage of binary search becomes apparent with large data sizes:
- For n=1000: Sequential search may require 1000 comparisons, while binary search needs only ~10.
- For n=10,000: Sequential search needs 10,000 comparisons, while binary search needs ~14.
Note: If data is unsorted, binary search cannot be used; sequential search is the only option.
6. Summary¶
- Sequential Search: Simple and easy to use, suitable for small data sizes, unordered data (or scenarios with frequent additions/deletions).
- Binary Search: Extremely efficient, suitable for large data sizes and ordered data (but requires data to be sorted first).
Choose the algorithm based on data “order” and “scale”: use binary search for large ordered data, and sequential search for small unordered data. This is the most reasonable approach!