Search Algorithms
Search is defined as finding the position of an element within a data structure. For example, searching for element 9 in the sequence (21, 31, 11, 9, 1, 0, 22) would successfully locate 9 at index 3. Here are several search algorithms:
Linear Search
Linear search is an algorithm used for unordered data structures. It compares each element in the data structure sequentially until the target element is found. Using our previous example, we start searching from 21, which doesn't match, then check 31, which also doesn't match, then 11, and finally find 9.
The time complexity of linear search is O(n), where n is the number of elements in the array. The best case occurs when the target element is the first element in the array, while the worst case happens when the target element doesn't exist in the array or is the last element.
Binary Search
Binary search is particularly useful for ordered lists. The algorithm starts from the middle of the array and, if the element hasn't been found, reduces the search space by half. Here's the pseudocode:
BEG = lower_bound and END = upper_bound
MID = (BEG + END) / 2
If VAL < A[MID], then VAL will appear in the left segment of the array; END will be changed to: END = MID - 1
If VAL > A[MID], then VAL will appear in the right segment of the array; BEG will be changed to: BEG = MID + 1
For example, searching for element 9 in (0, 1, 9, 11, 21, 22, 34):
BEG = 0, END = 6
Middle value is 3, check index 3: 11 > 9. Set END = MID - 1 = 3 - 1 = 2
Middle value is 1, check index 1: 1 < 9. Set BEG = MID + 1 = 2
Middle value is 2, found 9.
The time complexity of binary search is O(log₂n).
Interpolation Search
Interpolation search is an algorithm for uniformly distributed ordered lists. Consider an array [0, 10, 20, 30, 40, 50, 60, 70, 80, 90], where each adjacent element differs by 10, satisfying uniform distribution. To find element 70, we first calculate the expected proportion of elements less than or equal to 70: p = (70 - 0) / (90 - 0) = 7/9. With array length n = 10, the expected index is n × p = 7, corresponding to element 70, which is exactly what we're looking for. This improves efficiency significantly compared to binary search.
The interpolation search algorithm follows the same approach as binary search, with one key difference: the element compared with the target is not the middle element of the search region, but rather calculated using this formula:
Mid = Begin + ((End - Begin) / (A[End] - A[Begin])) * (X - A[Begin])
Where:
Mid: Calculated element position
End: Position of the last element in the search region
Begin: Position of the first element in the search region
X: Target element to find
A[]: The entire sequence to be searched
Jump Search
Jump Search is similar to binary search, designed for ordered sequences, but it finds the target by examining fewer elements. It uses a fixed jump interval, making it more efficient than binary search in many cases.
For example, given an array arr of size n and jump interval m, we search indices arr[0], arr[m], arr[2m]...arr[km], etc.
Consider the array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). The array length is 16. Jump search will find 55 in the following steps, assuming a block size of 4:
Step 1: Jump from index 0 to index 4
Step 2: Jump from index 4 to index 8
Step 3: Jump from index 8 to index 16
Step 4: Since element at index 16 is greater than 55, we step back to index 9
Step 5: Perform linear search from index 9 to find element 55
The optimal block size to skip is O(√n). This gives jump search a time complexity of O(√n). The time complexity of jump search falls between linear search (O(n)) and binary search (O(log n)).