有序表的折半查找是什麼

有序表的折半查找：取中間值為比較對象，如果給定的值和中間值的關鍵字相等，則查找成功；若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續找。

本文操作環境：Windows7系統，Dell G3電腦。

折半查找概念：

折半查找，又稱為二分查找。

前提是線性表中的記錄必須是關鍵碼有序(由小到大或由大到小)，線性表必須採用順序儲存。

折半查找的基本想法是：在有序表中，取中間值為比較對象，如果給定的值和中間值的關鍵字相等，則查找成功；若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續尋找；若給定的值大於中間值的關鍵字，則在中間記錄的右半區繼續尋找。重複上述過程，直到尋找成功，或尋找所有區域無記錄，返回尋找失敗。

演算法實作：

public int Binary_Search(int[] a, int n, int key) {
int low = 1, high = n, mid;
while(low <= high) {
mid = (int)((low + high) / 2);
if(key < a[mid]) {
high = mid - 1;
}
else if(key > a[mid]) {
low = mid + 1;
}
else return mid;
}
return 0;
}

通常會使用三個指標low，high，mid。分別表示查找區域的最左值下標，找出區域的最右值下標，已經目前比對值下標。

時間複雜度分析：

折半查找其實等於是把靜態有序查找表分成了兩棵子樹，即查找經過只需要找其中的一半數據即可，等於工作量少了一半，以提升效率。

相關影片推薦：PHP程式設計從入門到精通

以上是有序表的折半查找是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！