二分法查找 C++

二分法查找 c++~

int binary_search(int *a, int length, int n) //length为数组长度， n为要查找的数
{
if(na[length-1])return -1; //没有合适的数
int left=0, right=length-1， middle;
while(left<right)
{
middle=(left+right)/2;
if(n>a[middle])left=middle;
else if(n<a[middle])right=middle;
else break; //这时求的值为n的数组下标，为middle；
}
while(middle>=0) //若有重复的n, 查找最前面的位置
{
if(a[middle]!=a[middle-1])return middle;
middle--;
}
}

#include
using namespace std;
int main()
{
void binarysearch(int[],int);
int a[]={2,3,6,11,20,25,33,36,56,58,59,69,76,86,89,99};
int i;
for(i=0;i<16;i++)
{
cout<<a[i]<<' ';
}
cout<<endl;
cout<<"input the no you will search:"<<endl;
int no;
cin>>no;
cout<<"input the number:"<<endl;
int b[20];
for(i=0;i<no;i++) //no若大于20则程序无法执行
cin>>b[i];
cout<<"now implement the search:"<<endl;
for(i=0;i<no;i++)
{
binarysearch(a,b[i]);
}
return 0;
}

void binarysearch(int a[],int key)
{
int low=0,high=15,mid;int found=0;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==key) found=1;
else if(a[mid]<key)
low=mid+1;
else
high=mid-1;
}
if(found)
cout<<key<<" in the array "<<"YES!"<<endl;
else
cout<<key<<" in the array "<<"NO!"<<endl;
}

在VC6.0中运行通过。
》代码一：（在代码三中指出了您没注意到的一些问题）》》：
#include<iostream>
using namespace std;
int main(void)
{
int BinSearch(int R[10],int K,int n);
int a[10],x,i,result;
for(i=0;i<10;i++)
cin>>a[i];
cin>>x;
result=BinSearch(a,x,10);
cout<<result<<endl;
return 0;
}
int BinSearch(int R[10],int K,int n)
{ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=0,high=n-1,mid; //置当前查找区间上、下界的初值
mid=(low+high)/2;
while(low<=high&&R[mid]!=K)
{ //当前查找区间R[low..high]非空
if(R[mid] >K)
high=mid-1; //继续在R[low..mid-1]中查找
if(R[mid] <K)
low=mid+1; //继续在R[mid+1..high]中查找
mid=(low+high)/2;
} //BinSeareh
if(R[mid]==K) return mid; //查找成功返回
else return -1; //当low>high时表示查找区间为空，查找失败
}
其实如果是在10个数中查找的话，参数n完全没必要
》代码二：》》：
#include<iostream>
using namespace std;
int main(void)
{
int BinSearch(int R[10],int K);
int a[10],x,i,result;
for(i=0;i<10;i++)
cin>>a[i];
cin>>x;
result=BinSearch(a,x);
cout<<result<<endl;
return 0;
}
int BinSearch(int R[10],int K)
{ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=0,high=10-1,mid; //置当前查找区间上、下界的初值
mid=(low+high)/2;
while(low<=high&&R[mid]!=K)
{ //当前查找区间R[low..high]非空
if(R[mid] >K)
high=mid-1; //继续在R[low..mid-1]中查找
if(R[mid] <K)
low=mid+1; //继续在R[mid+1..high]中查找
mid=(low+high)/2;
} //BinSeareh
if(R[mid]==K) return mid; //查找成功返回
else return -1; //当low>high时表示查找区间为空，查找失败
}
》代码三：》》：
如果您想在若干个（也就是您输入的元素个数不固定）你输入的元素中查找一个数，可以加一个参数n，用它传递数组中元素的个数
#include<iostream>
using namespace std;
int main(void)
{
int BinSearch(int R[10],int K,int n);//函数声明，如果定义在main函数之前，可以不要函数声明 具体参照参照xiang__198的代码
int a[100],x,i,result;
int num;
cout<<"您想输入几个数？"<<endl;
cin>>num;
cout<<"请输入"<<num<<"个已经由小到大排好序的数："<<endl;
for(i=0;i<num;i++)
cin>>a[i];
cout<<"请输入待查找的数："<<endl;
cin>>x;
result=BinSearch(a,x,num);//由于定义的函数要返回一个函数值，所以在主函数中要定义一个变量来接收这个返回值，数组元素做实参传递的是数组元素的首地址。故这里的调用写成result=BinSearch(a,x,num);，其中的a代表的是数组的首地址
cout<<"查找结果："<<endl;
cout<<result<<endl;
return 0;
}
int BinSearch(int R[10],int K,int n)//不能写成int BinSearch(int R[10],int K,n)，注意形参不能为一个常量int BinSearch(int R[10],int K,10) 也不对
{ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=0,high=n-1,mid; //置当前查找区间上、下界的初值
mid=(low+high)/2;
while(low<=high&&R[mid]!=K)//查找区间不为空时，如果查找到，则R[mid]!=K，结束循环，否则缩小查找空间继续查找，你的这里少了一个R[mid]!=K，所以即使查找到，也不会输出查找结果，因为形成了死循环
{ //当前查找区间R[low..high]非空
if(R[mid] >K)
high=mid-1; //继续在R[low..mid-1]中查找
if(R[mid] <K)
low=mid+1; //继续在R[mid+1..high]中查找
mid=(low+high)/2;
} //BinSeareh
if(R[mid]==K)return mid; //查找成功返回
else return -1; //当low>high时表示查找区间为空，查找失败
}
对我的回答有疑问可以Hi我！恭候！

int BinSearch(int R[10],int K,10) 这个10肯定是不对的 去掉就可以，一般作为模板的话，应该加个参数 int n 表示数组的大小
程序我测试了，是对的可以把那个10去掉。

这个函数可以扩展下，变成任意大小数组的二分查找。

刚好今天做过！
#include<iostream>
using namespace std;

int BinSearch(int R[10],int K)
{ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=0,high=9,mid; //置当前查找区间上、下界的初值
while(low<=high)
{ //当前查找区间R[low..high]非空
mid=(low+high)/2;
if(R[mid]==K) return mid; //查找成功返回
else if(R[mid] >K)
high=mid-1; //继续在R[low..mid-1]中查找
else
low=mid+1; //继续在R[mid+1..high]中查找
}
return -1; //当low>high时表示查找区间为空，查找失败
} //BinSeareh

int main()
{
int K,m,R[10]={1,2,3,4,5,6,17,28,39,110};
cout<<"请输入查找的数："<<endl;
cin>>K;
m=BinSearch( R, K);
if(m==-1) cout<<"该数不存在"<<endl;
else cout<<"该数存在 "<<m+1<<endl;
return 0;
}

---

珠晖区18672027077： 二分法查找 C++假设一维数组a[10]中的10个元素是按从小到大的顺序有序排列的,编写程序从a中二分查找出其值等于给定值x的元素,其中查找功能由函数... - ？
芒甄板苏：[答案] 在VC6.0中运行通过.》代码一:(在代码三中指出了您没注意到的一些问题)》》:#includeusing namespace std;int main(void){int BinSearch(int R[10],int K,int n);int a[10],x,i,result;for(i=0;i>a[i];cin>>x;res...

珠晖区18672027077： C++用递归写个二分法查找 - ？
芒甄板苏： 递归法实现,构造函数.c++程序,试一下:#include using namespace std; int search(int [],int,int,int); int main() { int key; int word[]={1,3,6,9,12,14,17,19,22,24,25}; int left=0; int right=sizeof(word)/sizeof(int)-1; //计算数组长度写得不正确 int result; ...

珠晖区18672027077： C++ 输入10个数(有序),用二分法进行查找某个数是否在其中. - ？
芒甄板苏： #include using namespace std; //a是查找的数组,二分法查找的前提条件是a数据的排序是有序的.key是待查找的变量,n是数组a的长度. int binary( int *a, int key, int n ) { int left = 0, right = n - 1, mid = 0; mid = ( left + right ) / 2; while( left < right &...

珠晖区18672027077： 二分法查找 c++？
芒甄板苏： 参考例子: #include &lt;search.h&gt; #include &lt;string.h&gt; #include &lt;stdio.h&gt; int compare(const void *elem1, const void *elem2) { const int e1 = *(const int *)(elem1); const int e2 = *(const int *)(elem2); return (e1 == e2) ? 0 : ((e1 &lt; e2) ? -1 ...

珠晖区18672027077： C++数组二分法查找 - ？
芒甄板苏： O指数组的二分的开始位置,H为结束位置.比如:1 2 3 4 5 6 7 8 9 01 2 3 4 5 | 6 7 8 9 0 有: O=0;H=4;O=4;H=9;1 2 3 | 4 5 | 6 7 8 | 9 0 有 O=0;H=2;O=3;H=4;O=5;H=7;O=8;H=9;

珠晖区18672027077： 二分法查找 C++ - ？
芒甄板苏： 在VC6.0中运行通过.》代码一:(在代码三中指出了您没注意到的一些问题)》》:#include<iostream> using namespace std; int main(void) { int BinSearch(int R[10],int K,int n); int a[10],x,i,result; for(i=0;i<10;i++) cin>>a[i]; cin>>x; result=...

珠晖区18672027077： C++二分法查找数组中不超过某个数的最大元素的函数? - ？
芒甄板苏： 例如某数组存放值为2468889现在查找小于9的最大值个数,有三个8,所以输出为3

珠晖区18672027077： 求救,能用c语言帮写个二分查找吗?用c++运行的!越简单越好! - ？
芒甄板苏： 二分查找是建立在单调的有序数列的基础上,比如说你要在一个单调递增的区间里找一个数,你可以每次选择当前区间的中间一个数,和你要找的数相比,如果中间那个数大,那么你要找的数则在当前区间的前一半,所以把前一半区间当作当前...

珠晖区18672027077： c++binary - search函数怎么用 - ？
芒甄板苏： 二分法检索(binary search)又称折半检索,二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组(array)中, 首先将给定值key与字典中间位置上元素的关键码(key)比较,如果相等,则检索成功; 否则,若key小,则在字典前半部分中继续进行二分法检索; 若key大,则在字典后半部分中继续进行二分法检索. 这样,经过一次比较就缩小一半的检索区间,如此进行下去,直到检索成功或检索失败. 二分法检索是一种效率较高的检索方法,要求字典在顺序表中按关键码排序.

珠晖区18672027077： C++ 二分法查找 - ？
芒甄板苏： if(a[mid]==key) found=1;改为:if(a[mid]==key) { found=1;break;}