二分法基本上学计算机的都听过,但是有人不知道的就是其实二分法是减治法的思想。
所谓减治法和分治法有一个主要差别就是减治法是减去一般,就是分治之后只需要解决原问题的一半就可以了得到全局问题的解了。所以速度很快。
下面是二分法的递归程序和非递归程序和主测试程序:
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
int recurBiSearch(const vector<T> &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<typename T>
int iterBiSearch(vector<T> &vt, T key, int low, int up)
{
int mid;
while (low<=up)
{
mid = (low+up)>>1;
if(key<vt[mid])
up = mid - 1;
else if(vt[mid]<key)
low = mid + 1;
else return mid;
}
return -1;
}
int main()
{
std::vector<int> 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<vec.size();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<<ind;
cout<<"\tValue: "<<vec[ind]<<endl;
cout<<"Iterative Search Index Position: ";
ind = iterBiSearch(vec, 20, 0, vec.size()-1);
cout<<ind;
cout<<"\tValue: "<<vec[ind]<<endl;
system("pause");
return 0;
}
运行结果:
分享到:
相关推荐
int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则返回-1; int mid=(low+high)/2; if(low>high){ return -1;//该元素不在数组中 } if(a...
这是一个用c++做的简单的折半查找算法,在递增的序列数组中,找到对应的数字的位置
binary sort,二分法查找,binary search, 二分法排序,merge sort 混合排序,shell sort 希尔排序,insertion sort 插入排序。数据结构 data structure
课本上的二分查找的实现。有初始化,赋值,搜索三个操作
九章算法之二分法(Binary Search) 适合找工作的小伙伴
A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value, by comparing an ...
binary search tree 二叉搜索树的C++实现,有插入、删除、查找、查找最大最小等功能,并附有测试例子,简单易懂
使用二分递归查找int型的值,很简单的Demo
c++ 二分搜索树 二分查找树 binary search tree BST
c++ 封装 二叉排序树 私有成员函数递归 非递归的插入 实现的树的各种操作,并且利用c++的面向对象思想进行封装,内部包含三个文件BinaryTree.cpp, BinaryTree.hpp , main.cpp
matlab开发-BinarySearch。对数据向量中的值进行二进制搜索。
Binary Search Tree 利用C++實現 Binary Search Tree
class binary_search { public: int * arr; int nElems; public : binary_search(); binary_search(int max); virtual ~binary_search(); int find(int searchKey); void insert(int value); void ...
matlab开发-Binarysearch。bsearch对已排序的数组执行二进制搜索
NULL 博文链接:https://enria.iteye.com/blog/1441105
CatCafe:我正在进行的一个项目是使用Java Binary Search Trees,递归和Tree Traversal提出由三叉树CatTree代表的猫的数据库
二叉树的4个非递归算法,中序先序后序和层次遍历,算法都有注释而且很详细,适合数据结构学习者使用
最小成本二分检索树optimal binary optimal binary
课上组内共同完成,由导师监督。有一定参考价值
http://blog.csdn.net/xkzju2010/article/details/46399155