二分搜索法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛,而且它的思想易于理解,但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了,但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing
Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定,正确地归纳奇偶数的各种情况,其实整理后可以发现它的具体算法是很直观的,我们可用C++描述如下:
#include"iostream.h"
int main()
{ int bs(int a[],int y,int n);
int a[10]={1,5,6,32,36,56,62,74,98,150};
int y=56;
int i=bs(a,62,10);
cout<<"我求的是在数组a,a[10]={1,5,6,32,36,56,62,74,98,150}中找数字56的位置"<<endl;
if(i==-1)
cout<<"这个数不在数组中"<<endl;
else
cout<<"这个数是数组的第"<<i+1<<"个数"<<endl;
return 0;
}
int bs(int a[],int y,int n)
{
int right=n-1;
int left=0;
int midd;
while(left<=right)
{
midd=(left+right)/2;
if(y==a[midd])
return midd;
if(y>a[midd])
left=midd+1;
else
right=midd-1;
}
return -1;
}
分享到:
相关推荐
二分搜索算法的实现,整合了冒泡排序,虽然用的是很常规的东西,但是是自己认真在做的,算是自己程序之路上的一个小小收获吧。
二分搜索法
二分搜索法 其中包含三个文件求其解析解太难 用二分法 快速搜索 并保证其一定的精度
设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。
算法设计与分析中关于二分搜索树的课件,大家可以看一下,高手就不必了吧。
算法分析 二分搜索算法 实验报告 包含实验目的 试验分析和程序代码
算法的实验,背包问题,二分搜索_快速排序_背包问题,若有兴趣可以下载使用。
一个小编程 关于二分搜索法的实验,有需要的可以看看。
一个典型的C++实现的二分搜索算法,实现从文件读取操作数。
分治法实现二分搜索(c语言)
实现二分搜索树的查找、删除、输出 包含构造很析构函数
设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j
用java实现二分搜索,由用户输入十个数,若十个数不是升序,则重新输入,若按升序输入则输入用户要查找的数,最后输出用户要查找的数在输入数列的位置。内附实验截图
设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时,I和j相同,均为x在数组中的位置。
用C语言动态实现二分搜索算法,可以清楚的看到算法之行的全部过程。
这是采用递归分治算法写的二分搜索算法, 是为上机考试准备的,呵呵呵
本文档详细描述了算法分析与设计中,二分搜索算法的详尽解释,适合算法初学者。
个人编写的二分搜素算法,可以从大到小搜索,也可从小到大搜索
关于数值算法中二分搜索的一些东西,比如求两个函数的交点。
这是一个动态规划的二分搜索算法的程序 内容包括注释 及源代码 直接下载复制就可运行 其中还包含一个简易的数据生成器