ACM二分搜索算法

二分搜索算法就是把要搜索的数据在搜索文本中根据情况进行折半，比如要在2 6 4 9 3 8 7 3 5中找到找到4的位置，那么可以考虑先把数据进行排序，然后把拍好后的数据的中间的那个数据和要查找的数据4进行比较，如果中间的数据比4大，那么4肯定在左半边（即最小数据到中间数据这边），既然这样，那又在这左半边数据中进行同样的操作不就可以找到4咯；听起来就是递归的样子。

用上面的例子演示一下数据是：2 6 4 9 1 8 7 3 5；要查找的数据是4。先进行排序：1 2 3 4 5 6 7 8 9；中间的数据就是5；4<5；所以就在左半边（即：1 2 3 4）查找；然后左半边的中间值就是：2,2<4；所以就在右半边（即使是：3 4）查找；右半边的中间值是：3,3<4;所以又在右半边（4）查找；4==4；就找到了；

Tips：我们先把数据存到数组里面，然后用快排对数组进行排序；这个中间值的确定是这样子的：mdi=(low+hight)/2，low和hight都是指数组的下标；

下面贴代码：

我的：

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

    int n,key,mid;

    cin>>n;

    int *s=new int [n];

    for(int i=;i<n;i++)

    {   cin>>s[i];   }

    int low=,height=n;

    cin>>key;

    sort(s,s+n);

    while(low<=height)

    {

        mid=(low+height)/;

        if(key<s[mid])    height=mid-;

        else if(key>s[mid]) low=mid+;

        else break;

    }

    cout<<"key在数组中的下标是："<<mid<<endl;

    return ;

}

然后听大神说还有个5行就搞定的二分搜索法，于是就check了一下：

代码：

//二分查找：

#include <iostream>

#include <algorithm>

using namespace std;

int binSearch(int* a, int begin, int end, int k) //a是数组，begin是数组的开始下标，end是数组的结束下标

{

    int mid = begin + ( (end - begin)>> );

    int index;

    index = a[mid] < k && begin +  < end ? binSearch(a,mid+,end,k) :

        ( a[mid] > k && begin +  < end ? binSearch(a,begin,mid,k) :

        mid * (a[mid] == k) + (a[mid] != k)*(-));

    return index;

}

int main()

{

    int t;

    cin>>t;

    int*s=new int[t];

    for(int i=;i<t;i++)

    {

        cin>>s[i];

    }

    sort(s,s+t);

    int key;

    cin>>key;

    cout<<binSearch(s,,t-,key)<<endl;

    return ;

}

Sample:

6(数据的数量）

1 6 9 7 2 3（数据）

3（要查找的数据）

Sample Output:

5行二分搜索的链接：http://www.cnblogs.com/zhengyuhong/p/3660757.html

巴特西

ACM二分搜索算法

最新文章

热门文章