线性查找(Linear Search):
时间复杂度：O(n)
int linerSearch(int * array, int n, int x) { for (int i = 0; i < n; i++) { if (array[i] == x) return i; } return -1; }
二分查找(Binary Search):
T(n) = T(n/2) + 2
时间复杂度：Θ(log2(n))
如果将数组分为三组进行查找值，所需的比较次数为T(n/3) + 4 => 4 * c * log3n = (4 / log23) * log2n。因为4 / log23大于2，即所需比较次数大于二分发的2 * log2n
/* recursive version */ int binarySearch(int *array, int left, int right, int x) { if (left <= right) { int middle = left + ((right - left) >> 1);if (array[middle] == x) return middle; else if (array[middle] > x) return binarySearch(array, left, middle - 1, x); else return binarySearch(array, middle + 1, right, x); } return -1; } /* iteration version */ int binarySearch(int *array, int left, int right, int x) { int middle; while (left <= right) { middle = left + ((right - left) >> 1);if (array[middle] == x) return middle; else if (array[middle] > x) right = middle - 1; else left = middle + 1; } return -1; }
插值查找(Interpolation Search) :
适合已排序数组，并且元素的值是均匀分布的
时间复杂度：平均情况为log(log(n))、最坏情况下为 O(n)
int interpolationSearch(int *array, int n, int x) { int left = 0, right = n - 1; int pos; while (left <= right && x >= array[left] && x <= array[right]) { pos = left + (x - array[left]) / (array[right] - array[left]) * (right - left); if (array[pos] == x) return pos; if (array[pos] < x) left = pos + 1; else right = pos - 1; } return -1; }
跳查找(Jump Search)：
时间复杂度： O(√n)
int jumpSearch(int *array, int n, int x) { int prev, step, interval; prev = 0; step = interval = sqrt(n); while (array[step] < x) { if (step > n - 2) return -1; prev = step; if (step + interval > n - 1) step = n - 1; else step += interval; } while (prev < step) { prev++; if (array[prev] == x) return prev; } return -1; }
指数查找(Exponential Search)：
时间复杂度: O(Log n)
对于无边界数组查找非常有用
int exponentialSearch(int *array, int n, int key) { if (array[0] == key) return 0; int i = 1; while (i < n && array[i] < key) { i = i << 1; } return binarySearch(array, i >> 1, i < n ? i : n - 1, key); }