有序表的折半查找有什么用

小編給大家分享一下有序表的折半查找有什么用，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

有序表的折半查找：取中間值為比較對(duì)象，如果給定的值和中間值的關(guān)鍵字相等，則查找成功；若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找。

折半查找概念：

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

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

折半查找的基本思想是：在有序表中，取中間值為比較對(duì)象，如果給定的值和中間值的關(guān)鍵字相等，則查找成功；若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定的值大于中間值的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。重復(fù)上述過(guò)程，直到查找成功，或查找所有區(qū)域無(wú)記錄，返回查找失敗。

算法實(shí)現(xiàn)：

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;
}

通常會(huì)使用三個(gè)指針low，high，mid。分別表示查找區(qū)域的最左值下標(biāo)，查找區(qū)域的最右值下標(biāo)，已經(jīng)當(dāng)前比對(duì)值下標(biāo)。

時(shí)間復(fù)雜度分析：

折半查找其實(shí)等于是把靜態(tài)有序查找表分成了兩棵子樹(shù)，即查找經(jīng)過(guò)只需要找其中的一半數(shù)據(jù)即可，等于工作量少了一半，以提升效率。

以上是“有序表的折半查找有什么用”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！