线性查找(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

时间复杂度：Θ(log₂(n))

如果将数组分为三组进行查找值，所需的比较次数为T(n/3) + 4 => 4 * c * log₃n = (4 / log₂3) * log₂n。因为4 / log₂3大于2，即所需比较次数大于二分发的2 * log₂n

 

/* 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);}