数据结构之查找

一、顺序查找法：时间复杂度为O（n）
二、有序查找法：前提是数据是有序的
１、二分查找法（折半查找法）：要定义头角标、中间角标、尾角标。
　　折半查找的时间复杂度是 O(logn)
　　如果涉及频繁的插入和删除，最好不要使用折半查找。
　　
例：数组查询

int max,mid,min
min=0;
max=arr.length-1;
min=(max+min)>>1;
while(arr[mid] != key){
if(key>arr[mid])
min=mid+1;
else if(key<arr[mid])
max=mid-1;
if(max<min)
return -1;
    mid=(max+min)>>1;

}

２、插值查找
　　插值查找将折半查找的角标变化的公式进行了改进 mid=min+key−arr[min]arr[max]−arr[min](max−min) ，时间复杂度依旧是 O(logn) ，但是如果表很大的话，插值查找算法的平均性能要比折半查找好得多。
３、裴波那契查找
　　事先设置一个裴波那契数列Ｆ＝｛0,1,1,2,3,5,8,13,21,34,55……｝
　　裴波那契查找的角标换算公式是 mid=min+F[k−1]−1 ，其时间复杂度是 O(logn) 。
　　

static int FibonacciSearch(int [] a, int n, int key){
int [] F = {0,1,1,2,3,5,8,13,21,34};
int low, high, mid, i, k;
            low = 1;
            high = n;
            k = 0;
while (n > F[k]-1) /* 计算n位于斐波那契数列的位置 */
                k++;

while (low <= high) {
mid = low + F[k-1] -1;
if (key < a[mid]){
                    high = mid - 1;
                    k = k - 1;
                }
else if (key > a[mid]){
                    low = mid + 1;
                    k = k - 2;
                }
else {
if (mid <= n)
                        return mid;
else
                        return n;
                }
            }
            return 0;
        }

　虽然他们的时间复杂度都是 O(logn) ，但是按平均性能：斐波那契>折半>插值。因为对于海量数据查找，折半查找是进行加法和除法运算，插值查找是进行四则运算，而斐波那契查找只有加减法运算。