溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下有序表的折半查找有什么用，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
有序表的折半查找：取中間值為比較對象，如果給定的值和中間值的關鍵字相等，則查找成功；若給定值小于中間記錄的關鍵字，則在中間記錄的左半區繼續查找。
折半查找概念：
折半查找，又稱二分查找。
前提是線性表中的記錄必須是關鍵碼有序(由小到大或由大到小)，線性表必須采用順序存儲。
折半查找的基本思想是：在有序表中，取中間值為比較對象，如果給定的值和中間值的關鍵字相等，則查找成功；若給定值小于中間記錄的關鍵字，則在中間記錄的左半區繼續查找；若給定的值大于中間值的關鍵字，則在中間記錄的右半區繼續查找。重復上述過程，直到查找成功，或查找所有區域無記錄，返回查找失敗。
算法實現：
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。分別表示查找區域的最左值下標，查找區域的最右值下標，已經當前比對值下標。
時間復雜度分析：
折半查找其實等于是把靜態有序查找表分成了兩棵子樹，即查找經過只需要找其中的一半數據即可，等于工作量少了一半，以提升效率。
以上是“有序表的折半查找有什么用”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
