折半查找(二分查找)

参考资料：
[1]大话数据结构 8.4 有序表查找

改进前：

//二分查找
#include<iostream>

using namespace std;

//输入
//查找的序列,数组最后一个元素的序号，要查找的数
//
int Binary_Search(int* a,int n,int key)
{
    int low= 0;
    int high = n;

    int mid;

    while(low<=high)
    {
        //步骤1：折半
        int mid = (low+high)/2;
        //步骤2：查找
        if(key<a[mid])//如果key小于a[mid],那么目标值在mid左边
            high = mid-1;
        else if(key>a[mid])//如果key大于a[mid],那么目标值在mid右边
            low = mid+1;
        else
            return mid;//目标值正好是位于这里
    }

}

int main()
{
    int a[] ={0,1,16,25,34,43,52,61,72,83,94};
    //要查找的数
    int key =94;
    //数组的个数
    int ilen=sizeof(a)/sizeof(a[0]);

    int found = Binary_Search(a,ilen-1,key);

    cout<<"found location"<<found<<endl;
}

折半查找的时间复杂度为O(logN),远远好于顺序查找的时间复杂度O(N)。
折半查找的前提是：有序表顺序存储。
顺序存储VS链式存储

改进后：

//二分查找，查找目标值所在的位置

int BinarySearch(int* a, int nLen, int nKey)
{
    if (a == nullptr|nLen<=0)
        return -1;//
    
    int nLow = 0;
    int nHigh = nLen - 1;

    while (nLow <= nHigh)
    {
        //折半查找
        int nMid = (nLow+nHigh)/2;
        if (nKey < a[nMid])
        {
            nHigh = nMid - 1;
        }
        else if(nKey>a[nMid])
        {
            nLow = nMid + 1;
        }
        else
        {
            return nMid;
        }
    }
    return -1;

}

int  BinarySearch(int *a, int nLeft, int nRight, int nKey)
{
    if (a == nullptr || nLeft > nRight)
        return -1;

    int nLow = nLeft;
    int nHigh = nRight;

    int nMid = (nLow+nHigh) / 2;

    if (a[nMid] < nKey)
        return BinarySearch(a, nMid + 1, nHigh, nKey);
    else if (a[nMid] > nKey)
        return BinarySearch(a, nLow, nMid - 1, nKey);
    else
        return nMid;

    return -1;

}





int main()
{
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    int nLen = sizeof(a) / sizeof(a[0]);
    //cout << nLen<<endl;
    //cout<<BinarySearch(a,nLen, 3);
    cout << BinarySearch(a, 0, nLen-1, 3);
    system("pause");
}