二分搜索算法

Question

设a[0],…,a[n-1]是已排好序的数组。改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
这是C语言课程设计里的分治策略

Answer 1

#include <stdio.h>

#include <stdlib.h>

int a[100]={1,2,3,5,12,12,12,15,29,55};//数组中的数（由小到大）

int k;

void found(int &x,int &y,int k) //在x与y之间，要找k 

{

if(x>y)return;

int m=x+(y-x)/2;

if(a[m]==k)x=y=m;

else if(a[m]>k)found(x,y=m-1,k);//找左边

else found(x=m+1,y,k);//找右边

}

int main()

{ int i=0,j=9;

scanf("%d",&k);//输入要找的数字k

found(i,j,k);//从数组a[0]到a[9]中找k 

if(i==j)printf("a[%d]==%d\n",i,k);

else printf("a[%d]==%d  a[%d]==%d,  k==%d\n",j,a[j],i,a[i],k);

return 0;

}

Answer 2

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用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++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。

参考资料：http://zhidao.baidu.com/question/1574912.html?fr=qrl3

本回答被提问者采纳

Answer 3

二分搜索的时候，是要慢慢缩小搜索范围的。比如一共有10个，那么middle是5,下一层搜索的范围应该是1-4和6-10。你的函数里没有这个功能。搜索函数至少应该是int
BinarySearch(Type
a[],
const
Type&
x,int
left,
int
right);终止条件就是if(left
>
right)

你定义y的时候是在main函数里，所以BinarySearch里面不能直接用y，解决方式是在外部定义一个全局的y变量，或者把y变量传到函数里。

Answer 4

我的C语言差点挂科了，我也不知道！

Answer 5

大汗．．．．这个问题是不是应该到电脑那边发布啊．．
我学音乐的，这个问题对我来说太难了．．．哭了．．．