Searching is the process of locating a specific element (the target or key) within a collection of data. If the element is found, the search returns its position (index); if not found, it typically returns -1 or an equivalent "not found" indicator. Efficient searching is critical in databases, file systems, and everyday applications.
Linear Search (Sequential Search)
Concept: Scan each element of the list one by one, from the first to the last, until the target is found or the list is exhausted.
- 1.Algorithm:
- 2.For i from 0 to n-1:
- 3.a. If list[i] == target: return i.
- 4.Return -1 (not found).
- Key Properties:
- Works on unsorted AND sorted data.
- Simple to implement.
- Time Complexity:
- Best case: O(1) — target is the first element.
- Average case: O(n/2) = O(n).
- Worst case: O(n) — target is last or absent.
- Space Complexity: O(1).
Search for 25 in [10, 40, 25, 8, 60].
- Check 10 (no), 40 (no), 25 (YES at index 2). Return 2.
Binary Search
Concept: Works only on a sorted list. Repeatedly divides the search interval in half. If the target is less than the middle element, search the left half; if greater, search the right half.
Algorithm (Iterative):
1. low = 0, high = n-1.
2. While low ≤ high:
a. mid = (low + high) // 2.
b. If list[mid] == target: return mid.
c. If list[mid] < target: low = mid + 1.
d. If list[mid] > target: high = mid - 1.
3. Return -1.
- Key Properties:
- Requires sorted data.
- Much more efficient than linear search for large data.
- Time Complexity:
- Best case: O(1) — target is at mid.
- Average / Worst case: O(log n).
- Space Complexity: O(1) iterative; O(log n) recursive (call stack).
Search for 35 in [10, 20, 30, 35, 40, 50].
- low=0, high=5; mid=2; list[2]=30 < 35, so low=3.
- low=3, high=5; mid=4; list[4]=40 > 35, so high=3.
- low=3, high=3; mid=3; list[3]=35 == 35. Return 3.
Comparison of Linear vs Binary Search
| Feature | Linear Search | Binary Search |
|---------|--------------|---------------|
| Prerequisite | None | Sorted list |
| Best case | O(1) | O(1) |
| Worst case | O(n) | O(log n) |
| Space | O(1) | O(1) iterative |
| Suitable for | Small/unsorted | Large/sorted |
How Many Steps? (log n intuition)
Binary search halves the search space each step. For n elements, it takes at most log2(n) + 1 comparisons.
Key formulas
This dramatic improvement over O(n) is why binary search is preferred for large sorted datasets.
Common mistakes
- Applying binary search to unsorted data — binary search will give INCORRECT results on unsorted lists.
- Integer overflow in mid calculation — mid = (low + high) // 2 is safe in Python; in some other languages, use low + (high - low) // 2.
- Off-by-one errors — conditions should be low ≤ high (not <) and updates should be mid+1 / mid-1 (not mid).
- Assuming linear search is always slower — for very small lists, linear search can be faster because binary search has overhead and requires sorting first.
Summary
Linear search checks elements one by one and works on any list. Binary search divides the search space in half each step but requires a sorted list. Binary search has O(log n) complexity versus O(n) for linear search, making it dramatically faster for large datasets. The choice between them depends on whether the data is sorted and how many searches are needed.