hdu2964-Prime Bases
二分查找的实现和使用标准库函数实现二分查找
算法思想：1、将数组排序(从小到大)；2、每次跟中间的数mid比较，如果相等可以直接返回，
如果比mid大则继续查找大的一边，否则继续查找小的一边。
输入：排序好的数组 - arrayname[]，数组大小 - array_size，查找的值 - searchnumber
返回：找到返回其在数组中位置，否则返回-1
二分查找的代码实现
int binary_search(int arrayname[], intarray_size, int searchnumber)
{
intlow = 0, high = array_size - 1, mid;
while(low <= high)
{
mid= (low + high) / 2;//获取中间的位置
if(arrayname[mid] == searchnumber)
returnmid; //找到则返回相应的位置
if(arrayname[mid] > searchnumber)
high= mid - 1; //如果比key大，则往低的位置查找
else
low= mid + 1; //如果比key小，则往高的位置查找
}
return-1;
}
代码示例：
（1） 将未排序数组排序
（2） 二分查找想查找的数字
（3） 显示查找结果
#include<iostream>
#include<algorithm>
using namespace std;
int binary_search1(int arrayname[], intarray_size, int searchnumber)
{
intlow = 0, high = array_size - 1, mid;
while(low <= high)
{
mid= (low + high) / 2;//获取中间的位置
if(arrayname[mid] == searchnumber)
returnmid; //找到则返回相应的位置
if(arrayname[mid] > searchnumber)
high= mid - 1; //如果比searchnumber大，则往低的位置查找
else
low= mid + 1; //如果比searchnumber小，则往高的位置查找
}
return-1;
}
int main()
{
int a[10]={9,6,3,8,5,2,7,4,1,0},i=0;
printf("未排序之前的数组里的每一个元素！\n");
for( i = 0 ; i < 10 ; i++ )
cout<<a[i]<<"\t";
cout<<endl;
sort(a,a+10);
printf("排序之后的数组里的每一个元素！\n");
for( i = 0 ; i < 10 ; i++ )
cout<<a[i]<<"\t";
//查找数组中存在的数字
i=binary_search1(a,10,5);
if(i)
{
cout<<"要查找的数字在数组中的位置是"<<i<<endl;
cout<<"该数字是"<<a[i]<<endl;
}
else
cout<<"没有该数字！"<<endl;
//查找数组中不存在的数字
i=binary_search1(a,10,20);
if(i>0)
cout<<a[i]<<endl;
else
cout<<"没有该数字！"<<endl;
system("pause");
return 0;
}
用标准库里的二分查找函数实现二分查找
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[10]={9,6,3,8,5,2,7,4,1,0},i=0;
printf("未排序之前的数组里的每一个元素！\n");
for( i = 0 ; i < 10 ; i++ )
cout<<a[i]<<"\t";
cout<<endl;
sort(a,a+10);
printf("排序之后的数组里的每一个元素！\n");
for( i = 0 ; i < 10 ; i++ )
cout<<a[i]<<"\t";
//查找数组中存在的数字
if(binary_search(a,a+10,5))
{
cout<<"要查找的数字在数组中"<<endl;
}
else
cout<<"没有该数字！"<<endl;
//查找数组中不存在的数字
if(binary_search(a,a+10,20))
cout<<a[i]<<endl;
else
cout<<"没有该数字！"<<endl;
system("pause");
return 0;
}
补充：软件开发 , C++ ,
