折半查找法：
在有序表中，把待查找數據值與查找范圍的中間元素值進行比較，會有三種情況出現：
1） 待查找數據值與中間元素值正好相等，則放回中間元素值的索引。
2） 待查找數據值比中間元素值小，則以整個查找范圍的前半部分作為新的查找范圍，執行1），直到找到相等的值。
3） 待查找數據值比中間元素值大，則以整個查找范圍的後半部分作為新的查找范圍，執行1），直到找到相等的值
4） 如果最後找不到相等的值，則返回錯誤提示信息。
按照二叉樹來理解：中間值為二叉樹的根，前半部分為左子樹，後半部分為右子樹。折半查找法的查找次數正好為該值所在的層數。等概率情況下，約為
log2(n+1)-1
復制代碼 代碼如下:
//Data為要查找的數組，x為待查找數據值，beg為查找范圍起始，last為查找范圍終止
//非遞歸法
int BiSearch(int data[], const int x, int beg, int last)
{
int mid;//中間位置
if (beg > last)
{
return -1;
}
while(beg <= last)
{
mid = (beg + last) / 2;
if (x == data[mid] )
{
return mid;
}
else if (data[mid] < x)
{
beg = mid + 1;
}
else if (data[mid] > x)
{
last = mid - 1;
}
}
return -1;
}
//遞歸法
int IterBiSearch(int data[], const int x, int beg, int last)
{
int mid = -1;
mid = (beg + last) / 2;
if (x == data[mid])
{
return mid;
}
else if (x < data[mid])
{
return IterBiSearch(data, x, beg, mid - 1);
}
else if (x > data[mid])
{
return IterBiSearch(data, x, mid + 1, last);
}
return -1;
}
//主函數
int _tmain(int argc, _TCHAR* argv[])
{
int data1[60] = {0};
int no2search = 45;
cout << "The array is : " << endl;
int siz = sizeof(data1)/sizeof(int);
for (int i = 0; i < siz; i++)
{
data1[i] = i;
cout << data1[i] << " ";
}
cout << endl;
int index = -1;
//index = BiSearch(data1, no2search, 0, siz);
index = IterBiSearch(data1, no2search, 0, siz);
cout << "Index of " << no2search << " is " << index << endl;
getchar();
return 0;
}
復制代碼 代碼如下:
/**
* 折半查找字符在數組中的位置(有序列表)
* @param array 被檢索的數組
* @param x 要查找的字符
* @returns 字符在數組中的位置，沒找到返回-1
*/
function binarySearch(array,x){
var lowPoint=1;
var higPoint=array.length;
var returnValue=-1;
var midPoint;
var found=false;
while ((lowPoint<=higPoint)&&(!found)){
midPoint=Math.ceil((lowPoint+higPoint)/2);
//console.log(lowPoint+"===="+midPoint+"===="+higPoint);
if(x>array[midPoint-1]){
lowPoint=midPoint+1;
}
else if(x<array[midPoint-1]){
higPoint= midPoint-1;
}
else if(x=array[midPoint-1]){
found=true;
}
}
if(found){
returnValue=midPoint;
}
return returnValue;
}
/*var array2=[1,2,3,4,5,6,7,8,9,100,109];*/
var array2=['a','b','c','d','e','f','g'];
console.log(binarySearch(array2,'c'));