二分法查找

二分法查找

算法：二分法查找适用于数据量较大，但是数据需要先排好序

(1)确定该区间的中间位置k
（2）将查找的值T与array[k]进行比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……，K-1]b.array[k]<T 类似上面查找区间为array[k+1,……，high]。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。时间复杂度为:O(log2n

算法复杂度分析

时间复杂度

1.最坏情况查找最后一个元素Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情况查找中间元素O(1)查找的元素即为中间元素（奇数长度数列的正中间，偶数长度数列的中间靠左的元素）
3.取最坏和最好的平均查找次数得出T(n)=O(logn)

空间复杂度

1.S(n)=n

算法c语言实现

//递归算法
int recurbinary(int *a, int key, int low, int high)
{
    int mid;
    if(low > high)
        return -1;
    mid = (low + high)/2;
    if(a[mid] == key) return mid;
    else if(a[mid] > key)
        return recurbinary(a,key,low,mid -1);
    else
        return recurbinary(a,key,mid + 1,high);
}
 
//非递归算法
int binary( int *a, int key, int n )
{
    int left = 0, right = n - 1, mid = 0;
    mid = ( left + right ) / 2;
    while( left < right && a[mid] != key )
    {
        if( a[mid] < key ) {
            left = mid + 1;
        } else if( a[mid] > key ) {
            right = mid;
        }
        mid = ( left + right ) / 2;
    }
    if( a[mid] == key )
        return mid;
    return -1;
}
int main()
{
    int a[] = {1,2,3,4,5,6,7,8,9,12,13,45,67,89,99,101,111,123,134,565,677};
    int b[] = {677,1,7,11,67};
    int i;
    for( i=0; i<sizeof(b)/sizeof(b[0]); i++ )
    {
        //printf( "%d\n", recurbinary(a, b[i],0,sizeof(a)/sizeof(a[0])-1) );
        printf( "%d\n", binary( a, b[i], sizeof(a)/sizeof(a[0])));
    }
    return 0;
}