二分搜索算法的应用题

‘壹’ 二分搜索问题

vara:array[1..10]ofinteger;i,j,n,x:integer;beginwriteln('输入10个从小到大的数：');fori:=1to10doread(a[i]);writeln('输入要查找的数：');readln(x);i:=1;n:=10;j:=trunc((i+n)/2);repeatifa[j]>xthenbeginn:=j-1;j:=trunc((i+j)/2)endelseifa[j]=n);{为什么是这个结束循环条件}ifa[j]=xthenwriteln('查找成功！位置是：',j:3)elsewriteln('查找失败，数组中无此元素！')end.

‘贰’ 现有升序数组a={1，3，4，7，9，15，21，24，26，33}，请用二分搜索算法确定24在数组中的位置

你好！

希望对你有帮助！

‘叁’ 二分搜索算法的实现

二分搜索的时候，是要慢慢缩小搜索范围的。比如一共有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变量传到函数里。

‘肆’ 二分搜索算法

#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 ",i,k);

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

return 0;

}

‘伍’ 实现二分搜索算法,并分析其时间复杂度

对于这样一个谓词f()，满足性质：若f(a)=true，则对于任意定义域内的b>a，f(b)=true.
l与r为值域
int work ( int begin , int end ) {
while ( end - begin != 1 ) {
const int middle = ( begin + end ) / 2 ;
if ( f ( middle ) ) end = middle ;
else begin = middle ;
}
return begin ;
}
返回的是最大的x使f(x)为否

‘陆’ 二分搜索算法是利用什么实现的算法

二分搜索算法是利用排除剩余元素中一半的元素实现的算法。

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索算法原理：

1、如果待查序列为空，那么就返回－1，并退出算法；这表示查找不到目标元素。如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。如果不相等，就再比较这两个元素的大小。

2、如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。

3、如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。

‘柒’ C语言递归函数如何实现二分搜索算法

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，已知一个有n个元素的有序序列, 将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x, 直到找到x或者是没有找到!

如果是常规的方法的话那么我们可以通过循环的方式, 按照上面说的算法, 找到则退出循环, 否则继续循环直到左下标位置小于或者等于右下标的位置.

按兄弟你的意思是要用递归方法进行搜索, 那么大概还是上面的算法, 只是把循环的方式改成递归方式: 如果没找到,则确定新的搜索范围, 即左右下标新位置, 然后把新的参数传给函数继续调用函数进行递归搜索!!

递归方式实现详细代码如下:

#include <stdio.h>

#define ARRAY_SIZE 10
#define NOT_FOUND -1

int BinarySearch(int array[], int left, int right, int NumToSearch)
{
int mid = (left + right) / 2;

if (left <= right)
{
if (NumToSearch == array[mid])
{
return mid;
}
else if (NumToSearch < array[mid])
{
right = mid - 1;
return BinarySearch(array, left, right, NumToSearch);
}
else
{
left = mid + 1;
return BinarySearch(array, left, right, NumToSearch);
}
}

return NOT_FOUND;
}

int main()
{
int a[ARRAY_SIZE] = {2, 5, 6, 7, 13, 20, 22, 27, 112, 222};//假设一个已知的有序且是升序数列
int result = 0;//查找的结果
int x = 13;//假设我们要查找的数是13
int left = 0;//序列开始下标
int right = ARRAY_SIZE - 1;//序列结尾下标

result = BinarySearch(a, left, right, x);
if (result == NOT_FOUND)
{
printf("Not Found!\n");
}
else
{
printf("Found %d in array a, it is a[%d]\n", x, result);
}

return 0;

}

希望对兄弟你有帮助!

‘捌’ 一个计算机查找的问题，100分送上，有加分100

你的数都没排序，线性遍历已经是最快的了，如果发现有重复就不插入，遍历到底都没重复就插入。否则只有一种办法，第一次插入的时候先排序，然后再遵照排序的规则往里面插入你要插入的数（就是说你完成插入之后不能破坏了那种序），这就有很多算法了，比如你把所有的数按递增或递减排序，然后你的插入就可以按照二分法插入，这种插入的算法复杂度是log(n)，其中log以2为底，n是你的数组的元素个数。另外也可以选择建立一棵二叉搜索树，堆排序或者归并排序。但是这些方法都涉及到排序，复杂度也不小，但是一劳永逸的，你第一次完成了排序，后面就只需要插入新的数后仍然维持这个序就可以了，但是序的维护如果算法不当工作量也不会小，甚至还不如线性遍历。所以这个问题本身具有一定的灵活性和多样性。需要针对具体情况做出相应的选择。关于这些排序算法，很多书上都有，或者在网上搜一搜也能搜得到。不过有一点楼主要记住，排序，搜索，插入三者可以说是牵一发动全身的关系，而牵着这一发的正是排序。排序工作做好了，搜索和插入一般情形下相对没排序时效率都会有所提升。而且这三者经常相伴出现，所以不要只想到提高其中一个的效率，而应该同时兼顾三者，考察它们配合时的整体效率！

‘玖’ 关于二分搜索和顺序搜索

答案是A。应用顺序查找法时，查找1需要比较1次；应用二分查找法时，查找1需要比较3次，总次数为4次。其他元素的总查找次数均超过4次。