关于查找问题的一些感悟

对于大多简单的查找，往往采用先排序后查找的方法可以使查找的操作变得简单，对于如何排序，上篇文章有说到，这里不再赘述。

对于一般的查找，可以使用暴力求解，也就是线性查找的方法，在查找次数很少的时候，采用这个方法的效果还不错。但对于需要大量查找操作的时候，线性查找往往不是一个很好的方法。此时一般选用二分查找，先对原来的数据进行排序，使用快速排序使得数据有序后，进行二分查找。原因如下：

假如需要查找m次，线性查找的复杂度为O(mn).而二分查找的时间复杂度为O(nlogn+mlogn).当m足够大时，此时线性查找的时间远大于二分查找。

下面说明二分查找的原理：

首先定义两个指针low和high，每次将需要查找的元素(x)和中间的元素A[mid]进行比较，如果x=A[mid],那么直接返回mid的值即可；如果x>A[mid],那么说明此时要查找的元素一定是在A[mid]的右边，那么此时改变low的值，low=mid+1,再进行上述操作；如果x<A[mid],原理相同，high=mid-1.那么什么时候结束上述的比较操作呢？其一：找到了x所在的位置，返回mid即可。其二：没有找到x所在的位置，当low的位置指向了high的位置后，此时所有元素均不符合，说明未找到。对mid有个问题需要注意，如果low和high的值都接近于最大整数时可能会出现溢出的情况，这里不能使用mid=(low+high)/2;需要使用mid = low + (high-low)/2;

具体实现代码如下：

int Binary(int A[],int n,int x){
    int low = 0,high = n-1;
    while(low <= high){
        int mid = low + (high-low)/2;
        if(A[mid]==x){
            return mid;
        }
        else if(A[mid]>x){
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return -1;
}