Searching Algorithms

Finding a value

• Searching 查找 means locating a target value in a collection.
• Two standard algorithms: linear search 线性查找 and binary search 二分查找.
• Both return the index where the target sits — or a "not found" signal (often -1).
• Which one you may use depends on whether the data is sorted.

Linear search

• Check each element from the start, one by one, until you find the target.
• for (int i = 0; i < a.length; i++) if (a[i] == target) return i;
• Works on any array — sorted or not.
• Worst case: it looks at every element (n checks).

Linear search checks every element in turn until the target is found

Binary search halves the range at each step

Binary search

• Needs a sorted 已排序 array. Look at the middle element each time.
• If the middle is the target, done. If the target is smaller, search the left half; if larger, the right half.
• Each step halves the range that's left to search.
• Far faster on large sorted arrays — about log₂ n checks, not n.

Why binary search is fast

• Linear search of a million items: up to a million checks.
• Binary search of a million sorted items: about 20 checks.
• The catch: the array must already be sorted.
• Halving repeatedly is the big idea behind O(log n).