Searching Techniques: Linear and Binary Search
Searching is the process of finding the location of a specific item (called the search key or target) within a collection of items (like an array). The two most fundamental searching algorithms are Linear Search and Binary Search.
1. Linear Search (Sequential Search)
Linear Search is the simplest search algorithm. It works by sequentially checking every element of the list (or array) until a match is found or the entire list has been searched.
How it Works (The Algorithm)
Start: Begin the search from the first element (index 0) of the array.
Compare: Compare the current array element with the target value (the item we are looking for).
Match:
If the current element matches the target value, the search is successful. The algorithm returns the index of that element and stops.
If the elements do not match, move to the next element in the array.
Repeat: Continue steps 2 and 3 until the target is found or the end of the array is reached.
Failure: If the end of the array is reached and the target was not found, the search is unsuccessful (often indicated by returning a value like -1).
Key Characteristics
No Requirement: The list does not need to be sorted (sorted or unsorted, it works the same way).
Simple Implementation: It is very easy to code and understand.
Time Complexity (Efficiency)
Time Complexity describes how the running time of the algorithm grows as the input size ($n$) increases.
| Scenario | Time Complexity | Description |
| Best Case | $O(1)$ (Constant Time) | The target element is the first element of the array. Only one comparison is needed. |
| Worst Case | $O(n)$ (Linear Time) | The target element is the last element or not present in the array. $n$ comparisons are needed. |
| Average Case | $O(n)$ (Linear Time) | On average, the search takes about $n/2$ comparisons. |
Conclusion: Linear Search is efficient only for small arrays or when the search element is often near the beginning.
2. Binary Search
Binary Search is a much more efficient searching algorithm, but it comes with a strict prerequisite: the array must be sorted (in ascending or descending order). It works by repeatedly dividing the search interval in half.
Prerequisite
The array must be sorted.
How it Works (The Algorithm)
Binary Search uses three pointers: Low (start index), High (end index), and Mid (middle index).
Initialize: Set Low to the first index (0) and High to the last index ($n-1$).
Calculate Mid: Calculate the Mid index using the formula: $Mid = \lfloor (Low + High) / 2 \rfloor$.
Compare: Compare the array element at the Mid index with the target value.
Match:
If $Array[Mid]$ equals the target, the search is successful. Return Mid.
Narrow the Search:
If the target is greater than $Array[Mid]$, it means the target must be in the upper half of the array. Discard the lower half by setting Low = $Mid + 1$.
If the target is less than $Array[Mid]$, it means the target must be in the lower half of the array. Discard the upper half by setting High = $Mid - 1$.
Repeat: Repeat steps 2 through 5 until the target is found or the Low pointer becomes greater than the High pointer (meaning the interval is empty and the element is not present).
Analogy: Think of searching for a word in a dictionary. You don't start at the first page (Linear Search); you open it to the middle, check if your word is before or after that page, and then repeat the process on the chosen half.
Key Characteristics
Efficiency: Much faster than Linear Search for large arrays.
Requirement: Strictly requires the array to be sorted.
Time Complexity (Efficiency)
| Scenario | Time Complexity | Description |
| Best Case | $O(1)$ (Constant Time) | The target element is the exact middle element of the array. |
| Worst Case | $O(\log_2 n)$ (Logarithmic Time) | The target is found at the very end of the search process, or not present. The search space is halved in each step. |
| Average Case | $O(\log_2 n)$ (Logarithmic Time) | The complexity remains logarithmic because the array size is drastically reduced in each step. |
Conclusion: Binary Search is highly efficient for large, static (non-changing) arrays where sorting is done once.
🆚 Comparison Summary
| Feature | Linear Search | Binary Search |
| Requirement | Array can be unsorted. | Array must be sorted. |
| Method | Sequential check, one by one. | Divide and Conquer (halving the search space). |
| Speed (Large Data) | Very Slow ($O(n)$) | Very Fast ($O(\log_2 n)$) |
| Complexity to Code | Easy to implement. | Moderate to implement. |