二分查找的實現和使用標准庫函數實現二分查找
算法思想：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;
}
