Search
Search is the process of locating whether a specific element exists and its exact position within a set of data. It is a fundamental operation involved in almost all programs.
Comparison of Three Search Algorithms
Linear Search O(n)
Does not require sorted data
Compare one by one, simple and reliable
Suitable for: small or unordered data sets
Binary Search O(log n)
Requires sorted data
Halve the range each time, eliminating half
Suitable for: general-purpose solution for sorted data
Interpolation Search O(log log n)
Requires sorted order + uniform distribution
Estimate position based on value proportion
Suitable for: optimal when data is uniformly distributed
Linear Search
Compare one by one starting from the first element until the target is found or the list is exhausted. Does not require the data to be sorted. Time complexity O(n).
Binary Search
Requires the data to be sorted. Each time compares with the middle element, reducing the search range by half. Time complexity O(log n).
Interpolation Search
An optimization of binary search. Instead of taking the middle point, it estimates the possible position based on the target value. When data is uniformly distributed, it can achieve O(log log n).
Example
/* Linear search: O(n), does not require sorted order */
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}
/* Binary search: O(log n), requires the array to be sorted (ascending) */
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2; /* Overflow-preventing calculation */
if (arr[mid] == target) return mid; /* Found */
if (arr[mid] < target)
left = mid + 1; /* Target is in the right half */
else
right = mid - 1; /* Target is in the left half */
}
return -1; /* Not found */
}
/* Interpolation search: O(log log n) average, requires uniformly distributed data */
int interpolationSearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
/* Interpolation formula: estimate position based on the proportional size of the value */
int pos = low + ((target - arr[low]) * (high - low))
/ (arr[high] - arr[low]);
if (arr[pos] == target) return pos;
if (arr[pos] < target)
low = pos + 1;
else
high = pos - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = 9;
printf("Linear search 50: index %d\n", linearSearch(arr, n, 50)); /* Output: 4 */
printf("Binary search 50: index %d\n", binarySearch(arr, 0, n-1, 50)); /* Output: 4 */
printf("Interpolation search 50: index %d\n", interpolationSearch(arr, n, 50)); /* Output: 4 */
return 0;
}
Complexity Comparison Summary
| Algorithm | Time Complexity | Requires Sorted | Applicable Scenarios |
|---|---|---|---|
| Linear Search | O(n) | no | Small data volume or unsorted |
| Binary Search | O(log n) | Yes | Sorted arrays, general and efficient |
| Interpolation Search | O(log log n)Average | Yes | Specific scenarios with uniformly distributed data |