首頁  >  文章  >  有序表的折半查找是什麼

有序表的折半查找是什麼

coldplay.xixi
coldplay.xixi原創
2021-01-26 16:59:035476瀏覽

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

有序表的折半查找是什麼

本文操作環境: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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn