Chinaunix首页 | 论坛 | 博客
  • 博客访问: 186129
  • 博文数量: 89
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 828
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-08 10:44
文章分类
文章存档

2014年(9)

2013年(80)

我的朋友

分类: C/C++

2013-11-14 16:16:32

二分法基本上学计算机的都听过,但是有人不知道的就是其实二分法是减治法的思想。
所谓减治法和分治法有一个主要差别就是减治法是减去一般,就是分治之后只需要解决原问题的一半就可以了得到全局问题的解了。所以速度很快。
下面是二分法的递归程序和非递归程序和主测试程序:
[cpp] view plaincopyprint?
#include  
#include  
using namespace std;  
  
template  
int recurBiSearch(const vector &vt, T key, int low, int up)  
{  
    if(low>up) return -1;  
    int mid = (low+up)>>1;  
    if (key < vt[mid])  
    {  
        return recurBiSearch(vt, key, low, mid-1);  
    }  
    else if (vt[mid] < key)  
    {  
        return recurBiSearch(vt, key, mid+1, up);  
    }  
    return mid;  
}  
  
template  
int iterBiSearch(vector &vt, T key, int low, int up)  
{  
    int mid;  
    while (low<=up)  
    {  
        mid = (low+up)>>1;  
        if(key             up = mid - 1;  
        else if(vt[mid]             low = mid + 1;  
        else return mid;  
    }  
    return -1;  
}  
  
int main()  
{  
    std::vector vec;  
  
    // set some initial content:  
    for (int i=1;i<10;i++) vec.push_back(i<<2);  
  
    vec.resize(7);  
    vec.resize(12,80);  
  
    std::cout << "vec contains:";  
    for (int i=0;i         std::cout << ' ' << vec[i];  
    std::cout << '\n';  
 
    //二分法特征:这里vec.size()-1和不减1都是可以的。  
    cout<<"Recurrence Search Index Position: ";  
    int ind = recurBiSearch(vec, 20, 0, vec.size()-1);  
    cout<     cout<<"\tValue: "<   
    cout<<"Iterative Search Index Position: ";  
    ind = iterBiSearch(vec, 20, 0, vec.size()-1);  
    cout<     cout<<"\tValue: "<   
    system("pause");  
    return 0;  
}  
阅读(335) | 评论(0) | 转发(0) |
0

上一篇:抽象工厂lua实现

下一篇:初始化JNI方法

给主人留下些什么吧!~~