Java中怎么實(shí)現(xiàn)一個(gè)二分法檢索算法

Java中怎么實(shí)現(xiàn)一個(gè)二分法檢索算法，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

成都一家集口碑和實(shí)力的網(wǎng)站建設(shè)服務(wù)商，擁有專業(yè)的企業(yè)建站團(tuán)隊(duì)和靠譜的建站技術(shù)，十載企業(yè)及個(gè)人網(wǎng)站建設(shè)經(jīng)驗(yàn) ,為成都1000+客戶提供網(wǎng)頁(yè)設(shè)計(jì)制作,網(wǎng)站開(kāi)發(fā),企業(yè)網(wǎng)站制作建設(shè)等服務(wù),包括成都營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，成都品牌網(wǎng)站建設(shè)，同時(shí)也為不同行業(yè)的客戶提供網(wǎng)站設(shè)計(jì)、網(wǎng)站制作的服務(wù),包括成都電商型網(wǎng)站制作建設(shè),裝修行業(yè)網(wǎng)站制作建設(shè)，傳統(tǒng)機(jī)械行業(yè)網(wǎng)站建設(shè),傳統(tǒng)農(nóng)業(yè)行業(yè)網(wǎng)站制作建設(shè)。在成都做網(wǎng)站,選網(wǎng)站制作建設(shè)服務(wù)商就選創(chuàng)新互聯(lián)。

一，二分法檢索算法介紹

二分法檢索（binary search）又稱折半檢索，二分法檢索的基本思想是設(shè)字典中的元素從小到大有序地存放在數(shù)組（array）中。是最常用的搜索算法之一，這主要是由于其搜索時(shí)間短。

二，二分法檢索算法思路

這種搜索使用分而治之方法，并且需要事先對(duì)數(shù)據(jù)集進(jìn)行排序。

它將輸入集合分為相等的兩半，并且每次迭代都將目標(biāo)元素與中間元素進(jìn)行比較。

如果找到該元素，則搜索結(jié)束。否則，我們根據(jù)目標(biāo)元素是小于還是大于中間元素，通過(guò)劃分并選擇適當(dāng)?shù)臄?shù)組分區(qū)來(lái)繼續(xù)尋找元素。

這就是為什么對(duì)Binary Search有一個(gè)排序的集合很重要的原因。

當(dāng)firstIndex（我們的指針）經(jīng)過(guò)lastIndex（最后一個(gè)元素）時(shí)，搜索將終止，這意味著我們已經(jīng)搜索了整個(gè)數(shù)組，并且該元素不存在。

有兩種方法可以實(shí)現(xiàn)此算法-迭代和遞歸。

這里不應(yīng)該是關(guān)于時(shí)間和空間這兩個(gè)實(shí)現(xiàn)之間復(fù)雜的差異，雖然這不成立于所有語(yǔ)言。

三，二分法檢索算法代碼實(shí)現(xiàn)

迭代式

首先讓我們看一下迭代方法：

public class SearchAlgorithms { /**  *迭代方法  * @param arr  * @param elementToSearch  * @return  */ public static int binarySearch(int arr[], int elementToSearch) {   int firstIndex = 0;  int lastIndex = arr.length - 1;   // 終止條件(元素不存在)  while(firstIndex <= lastIndex) {   int middleIndex = (firstIndex + lastIndex) / 2;   // 如果中間元素是我們的目標(biāo)元素，那么返回它的索引   if (arr[middleIndex] == elementToSearch) {    return middleIndex;   }    // 如果中間的元素比較小   // 將我們的指數(shù)指向中間+1，不考慮前半部分   else if (arr[middleIndex] < elementToSearch)    firstIndex = middleIndex + 1;     // 如果中間的元素更大    // 將我們的指數(shù)指向中間1，不考慮下半部分   else if (arr[middleIndex] > elementToSearch)    lastIndex = middleIndex - 1;   }  return -1; } /**  * 用于打印結(jié)果  * @param targetParameter  * @param index  */ public static void print(int targetParameter, int index) {  if (index == -1){   System.out.println(targetParameter + " 未找到");  }  else {   System.out.println(targetParameter + " 搜索結(jié)果為: " + index);  } } //測(cè)試一下 public static void main(String[] args) {  int index = binarySearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);  print(67, index); }}

輸出：

遞歸的

現(xiàn)在讓我們看一下遞歸實(shí)現(xiàn)：

遞歸方法的區(qū)別在于，一旦獲得新分區(qū)，我們便會(huì)調(diào)用方法本身。在迭代方法中，每當(dāng)確定新分區(qū)時(shí)，我們都會(huì)修改第一個(gè)和最后一個(gè)元素，并在同一循環(huán)中重復(fù)該過(guò)程。

這里的另一個(gè)區(qū)別是遞歸調(diào)用被推入方法調(diào)用堆棧，并且每個(gè)遞歸調(diào)用占用一個(gè)空間單位。

我們可以像這樣使用這種算法：

public class SearchAlgorithms {  /**  *遞歸方法  * @param arr  * @param elementToSearch  * @return  */ public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) {   // 結(jié)束條件  if (lastElement >= firstElement) {   int mid = firstElement + (lastElement - firstElement) / 2;    // 如果中間元素是我們的目標(biāo)元素，那么返回它的索引   if (arr[mid] == elementToSearch)    return mid;    // 如果中間元素大于目標(biāo)元素   if (arr[mid] > elementToSearch)    return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);    return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);  }   return -1; } /**  * 用于打印結(jié)果  * @param targetParameter  * @param index  */ public static void print(int targetParameter, int index) {  if (index == -1){   System.out.println(targetParameter + " 未找到");  }  else {   System.out.println(targetParameter + " 搜索結(jié)果為: " + index);  } } //測(cè)試一下 public static void main(String[] args) {  int index = recursiveBinarySearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 0, 10, 67);  print(67, index); }}

輸出：

四，以算法時(shí)間復(fù)雜度和空間復(fù)雜度總結(jié)算法。

時(shí)間復(fù)雜度

由于二進(jìn)制搜索每次將其時(shí)間復(fù)雜度為O（log（N））時(shí)都會(huì)將數(shù)組分為兩半。此時(shí)間復(fù)雜度是線性搜索O（N）時(shí)間復(fù)雜度的顯著改進(jìn)。

空間復(fù)雜度

此搜索僅需要一個(gè)空間單位即可存儲(chǔ)要搜索的元素。因此，其空間復(fù)雜度為O（1）。

如果二分法檢索是遞歸實(shí)現(xiàn)的，則需要將對(duì)該方法的調(diào)用存儲(chǔ)在堆棧中。在最壞的情況下，這可能需要O（log（N））空間。

它是大多數(shù)用于搜索的庫(kù)中最常用的搜索算法，二分法檢索樹(shù)也被許多存儲(chǔ)排序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)所使用。

該Arrays.binarySearch方法中的Java API也實(shí)現(xiàn)了二進(jìn)制搜索哦。

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。

本文名稱：Java中怎么實(shí)現(xiàn)一個(gè)二分法檢索算法
當(dāng)前地址：http://muchs.cn/article16/jpgidg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、域名注冊(cè)、ChatGPT、電子商務(wù)、關(guān)鍵詞優(yōu)化、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)