二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
Golang二分查找算法的簡單實現 http://www.linuxidc.com/Linux/2014-02/96093.htm
二分查找改進版 http://www.linuxidc.com/Linux/2013-10/91721.htm
二分查找的實現及注意事項 http://www.linuxidc.com/Linux/2013-07/87308.htm
用Python實現二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm
二分查找之Java實現 http://www.linuxidc.com/Linux/2012-05/59869.htm
Java針對數組的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm
算法要求:
1.必須采用順序存儲結構
.2.必須按關鍵字大小有序排列。
下面是c++與java的不同實現:
已經假設所查詢數組均為升序排列好了:
C++版:
#include <iostream>
#include <stdlib.h>
#define ERROR -1
#define LEN 10
using namespace std;
/************************************************************************/
/* T 自定義數據類型
value 查找的值
low 左側邊界 (一般為0)
high 右側邊界(一般為數組長度-1)
/************************************************************************/
template <class T>
int binarySearch(T table[],T value,int low,int hign){
if(low<=hign){//邊界有效
int mid = (low+hign)/2; //找到中間點
if(table[mid]==value){//如果中間點的值就是我們查找的值,則返回該點
return mid;
}else if(table[mid]>value){//如果中間值比查找值大,則證明查找的值在中間點的左側
return binarySearch(table,value,low,mid-1);//繼續將范圍縮小到原來一半(靠左縮小)
}else{
return binarySearch(table,value,mid+1,hign);//繼續將范圍縮小到原來一半(靠右縮小)
}
}
return ERROR;
}
/************************************************************************/
/* 由上述代碼可以知道,上邊界和和下邊界其實就是數組的開始和結束位置,因此上述函數可以泛化為下列函數 */
/************************************************************************/
template <class T>
int binarySearch(T table[],int n,T value){
return binarySearch(table,value,0,n-1);
}
template <class T>
void print(T table[],int n){
for (int i=0;i<n;i++)
{
cout<<table[i]<<" ";
}
cout<<"\n";
}
int main(void){
//給出一個已經排序好的數組
int array[LEN] = {0};
for (int i=0;i<LEN;i++)
{
array[i] = i+10;
}
cout<<"您要查找的序列為:";
print(array,LEN);
cout<<"請輸入你要查找的內容:";
int search;
cin>>search;
//調用函數
int searchResult = binarySearch(array,LEN,search);
cout<<"查找內容為"<<search<<"在指定數組的第"<<(searchResult+1)<<"處"<<endl;
system("pause");
return 1;
}
