实现二分法查找算法

㈠ 二分搜索算法的实现

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

㈡ 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;

}

希望对兄弟你有帮助!

㈢ 在线等~~~建立有10个元素的数组,实现二分法查找算法

满意的话，麻烦楼主火速采纳一下

#include<stdio.h>
int binsh(int *a, int e, int n)/*a是数组，e是要查找的元素，n是数组总元素的个数，e存在于a的话返回位置，否则返回-1*/
{
int low=0,high=n-1,mid;
for(mid=(low+high)/2;low<=high;mid=(low+high)/2)
{
if(e<a[mid])
high=mid-1;
else if(e>a[mid])
low=mid+1;
else
return mid;
}
return -1;
}
int main()
{
int a[]={1,2,3,4,5,6,7,8,9,0},n;
scanf("%d",&n);
printf("%d\n",binsh(a,n,10));
return 0;
}

㈣ 用顺序表实现二分查找算法

#include<iostream>
using namespace std;
int a[100];
int find1(int l,int r,int x)
{
int m=(l+r)/2;
if(l>r)//查找失败
return -1;
if(x==a[m])//查找成功返回下标
return m;
else if(x>a[m])
find1(m+1,r,x);//查找右边
else if(x<a[m])
find1(l,m-1,x);//查找左边
}
int main()
{//折半查找，待查找数列必须有序(升序或降序)
int x,n,num;
cin>>n;//输出n待查找数列长度
for(int i=0;i<n;i++)
cin>>a[i];//输入n个数
cin>>x;//输入查找值
num=find1(0,n,x);//调用折半查找函数(返回下标)
if(num!=-1)//数组下标0~n-1；返回-1查找失败
{
cout<<x<<":在数组中的位置 ";
cout<<num<<endl;
}
else
cout<<"查找失败"<<endl;
return 0;
}

㈤ 二分法查找算法

哪里查不到？我复制你的程序，输入字符c，结果显示“要查找的字符是第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)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。

㈦ 使用二分法查找算法的 前提条件是 被查数据必须是自然数对吗

前提是被查数据必须有序(升序或降序)。

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，如果当前位置arr[k]值等于key，则查找成功；若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；

若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，直到找到为止,时间复杂度:O(log(n))。

(7)实现二分法查找算法扩展阅读：

给定精确度ξ,用二分法求函数f(x)零点近似值的步骤如下:

1、确定区间[a,b],验证f(a)·f(b)<0,给定精确度ξ。

2、求区间(a,b)的中点c。

3、计算f(c).

(1) 若f(c)=0,则c就是函数的零点。

(2) 若f(a)·f(c)<0,则令b=c。

(3) 若f(c)·f(b)<0,则令a=c。

(4) 判断是否达到精确度ξ:即若|a-b|<ξ,则得到零点近似值a(或b),否则重复2-4。

㈧ 二分法的算法步骤是什么

在有序的有N个元素的数组中查找用户输进去的数据x。

算法如下：

1、确定查找范围front=0，end=N-1，计算中项mid=（front+end）/2。

2、若a[mid]=x或front>=end，则结束查找；否则，向下继续。

3.、若a[mid]<x，说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。

(8)实现二分法查找算法扩展阅读

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，

如果当前位置arr[k]值等于key，则查找成功；

若key小于当前位置值arr[k]，则在数列的前半段中查找，arr[low，mid-1]；

若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1，high]，

直到找到为止，时间复杂度:O(log(n))。

㈨ 二分法查找的算法

假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2.
1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。
2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。
3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。
如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。
例：在有序的有N个元素的数组中查找用户输进去的数据x。
算法如下：
1.确定查找范围front=0，end=N-1，计算中项mid=（front+end）/2。
2.若a[mid]=x或front>=end,则结束查找；否则，向下继续。
3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。
[一维数组，折半查找]

㈩ 二分法查找算法填空

j=r.length-1
//初始时，i和j为整个数组最小和最大的下标；
m=(i+j)/2
//m的值取i和j的中间数；
return
m
//如果这个
k值
等于m，则返回这个
m值
；
j=m-1
//否则如果这个k值小于m，则k只能出现在i到m-1之间；
i=m+1
//否则如果这个k值大于m，则k只能出想在m+1到j之间