折半查找法:
在有序表中,把待查找資料值與查找範圍的中間元素值比較,會有三種情況出現:
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
{
mid = (beg last) / 2;
if (x == data[mid] )
{
return mid;
}
else if (data[mid]
{
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
{
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
int siz = sizeof(data1)/sizeof(int);
for (int i = 0; i
{
data1[i] = i;
cout
}
cout
int index = -1;
//index = BiSearch(data1, no2search, 0, siz);
index = IterBiSearch(data1, no2search, 0, siz);
cout
getchar();
return 0;
}
/**
* 折半查找字元在陣列中的位置(有序列表)
* @param array 擷取的陣列
* @param x 要找的字元
* @returns 字元在陣列中的位置,找不到回傳-1
*/
函數binarySearch(數組,x){
var lowPoint=1;
var higPoint=array.length;
var 回傳值=-1;
var midPoint;
var 發現=假;
while ((lowPoint
midPoint=Math.ceil((lowPoint higPoint)/2);
//console.log(lowPoint "====" midPoint "====" higPoint);
if(x>array[midPoint-1]){
低點=中點1;
}
else if(x
higPoint= midPoint-1;
}
else if(x=array[midPoint-1]){
發現=真;
}
}
如果(找到){
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'));