考研时需要学习的一个算法，这里手打实现一个简单的折半查找

折半查找（二分查找）

介绍

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。
。

实现

递归

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};


//vector<int> array;

int BineraySearch(int* a,int left,int right,int target)//返回所在下标 
{
    if(left>right)
        return -1;
    int mid = (right - left) / 2 + left;
    cout<<left<<" "<<mid<<" "<<right<<endl;
    if(a[mid]<target)
    {
        left = mid + 1;
    }
    else if(a[mid]>target)
    {
        right = mid - 1;
    }
    else
    {
        return mid;
    }

    BineraySearch(a,left,right,target);
    
}


int main()
{

    int target=0;
    cin >> target;

    cout<<BineraySearch(a,1,10,target);
    return 0;
}

非递归

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int main()
{

    int target=0;
    cin >> target;

//    cout<<BineraySearch(a,1,10,target);
    int left=0;
    int right=9;
    while(left<=right)
    {
        int mid = (right - left) / 2 + left;
        cout<<left<<" "<<mid<<" "<<right<<endl;
        if(a[mid]<target)
        {
            left = mid + 1;
        }
        else if(a[mid]>target)
        {
            right = mid - 1;
        }
        else
        {
             cout<<mid<<endl;
             break;
        }
    }
    if(left>right)
        cout<<"Failed"!<<endl;
    return 0;
}