Java數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)折半查找的算法過程解析
折半查找技術(shù),也就是二分查找,通常稱為二分法查找。它的前期是線性表中的記錄必須是關(guān)鍵碼有序(通常從大到小有序),線性表必須采用順序存儲(chǔ)、折半查找的基本思想是:
取中間記錄作為比較對(duì)象,若給定值與中間記錄的關(guān)鍵字,則在中間記錄的關(guān)鍵字相等,則查找成功;若給定值小于中間記錄的做半,去繼續(xù)查找;若給定值大于中間記錄的關(guān)鍵字,則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程,直到查找成功,或所有查找區(qū)域無記錄,查找失敗為止。
在文本排重中需要用到折半查找,需要查找一個(gè)數(shù)組中是否存在某個(gè)數(shù)。
算法維護(hù)著一個(gè)上邊界hi,下邊界lo,使得要查找的值可能存在此之間,例如,我們要查找88這個(gè)數(shù):
初始化數(shù)據(jù)狀態(tài)
下面圖文示意查詢88二分法的流程
實(shí)現(xiàn)方式:
首先我們對(duì)要查找的數(shù)據(jù)排好序,然后用遞歸調(diào)用的方式實(shí)現(xiàn)折半查找,指定一個(gè)排好序的數(shù)組和要查找的值,同時(shí)指定左邊界和右邊界
/** * 尋找排好數(shù)組中的一個(gè)值 * * @param array 要查找的數(shù)組 * @param value 查找的值 * @param left 左邊界,這個(gè)值必須位于數(shù)組長(zhǎng)度區(qū)間內(nèi) * @param right 右邊界,這個(gè)值必須位于數(shù)組長(zhǎng)度區(qū)間內(nèi) * @return 找到的值在數(shù)組中的位置,如果沒找到就返回-1 * */ static int binarySearch(int[] array,int value, int left,int right){ if(left>right){ //退出條件 return -1; //沒有找到指定元素 } int mid =(left + right) >>>1 ;//相當(dāng)于mid=(left + right)/2 if(array[mid] == value){ return mid; }else if (array[mid] > value){ //遞歸調(diào)用查找左邊 return binarySearch(array,value,left,mid-1); }else { //遞歸調(diào)用查找右邊 return binarySearch(array,value,mid+1,right); } }
用非遞歸的方法實(shí)現(xiàn)折半查找
static int binarySearch(int[] array,int value, int left,int right){ int low = left;//開始位置 int high = right -1; //結(jié)束位置 while(low <= high){ int mid =(low + high)>>>1; //相當(dāng)于mid = (low + right)/2 int midVal = array[mid]; //取中間值 if(midVal < value){ //中間值小于要查找的關(guān)鍵字比較 low = mid +1; }else if(midVal > value){ //中間值大于要查找的關(guān)鍵字比較 high = mid -1; }else { return mid; //查找成功,返回找到的位置 } } return -(low+1); //沒找到,返回負(fù)值 }
需要注意的是:折半查詢依賴于排好序的數(shù)組。如果是一個(gè)沒有排好序的數(shù)組,則不能使用折半查找。首先需要排序處理。
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
Servlet實(shí)現(xiàn)共享數(shù)據(jù)JavaWeb組件的幾種方法
本文將結(jié)合實(shí)例代碼,介紹Servlet實(shí)現(xiàn)共享數(shù)據(jù)JavaWeb組件的幾種方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-07-07使用JavaBean根據(jù)指定條件設(shè)置屬性值默認(rèn)值方式
這篇文章主要介紹了使用JavaBean根據(jù)指定條件設(shè)置屬性值默認(rèn)值方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03Spring security實(shí)現(xiàn)權(quán)限管理示例
這篇文章主要介紹了Spring security實(shí)現(xiàn)權(quán)限管理示例,這里整理了詳細(xì)的代碼,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下。2017-01-01Java 并發(fā)編程:volatile的使用及其原理解析
下面小編就為大家?guī)硪黄狫ava 并發(fā)編程:volatile的使用及其原理解析。小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-05-05關(guān)于idea中Java Web項(xiàng)目的訪問路徑問題
這篇文章主要介紹了idea中Java Web項(xiàng)目的訪問路徑問題,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-03-03SpringMvc3+extjs4實(shí)現(xiàn)上傳與下載功能
這篇文章主要為大家詳細(xì)介紹了SpringMvc3+extjs4實(shí)現(xiàn)上傳與下載功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-06-06基于UncategorizedSQLException異常處理方案
這篇文章主要介紹了基于UncategorizedSQLException異常處理方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12