有序表的折半查找:取中間值為比較對象,如果給定的值和中間值的關鍵字相等,則查找成功;若給定值小於中間記錄的關鍵字,則在中間記錄的左半區繼續找。
本文操作環境: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中文網其他相關文章!