Java中怎么實現一個二分法檢索算法

Java中怎么實現一個二分法檢索算法，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

一，二分法檢索算法介紹

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

二，二分法檢索算法思路

這種搜索使用分而治之方法，并且需要事先對數據集進行排序。

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

如果找到該元素，則搜索結束。否則，我們根據目標元素是小于還是大于中間元素，通過劃分并選擇適當的數組分區來繼續尋找元素。

這就是為什么對Binary Search有一個排序的集合很重要的原因。

當firstIndex（我們的指針）經過lastIndex（最后一個元素）時，搜索將終止，這意味著我們已經搜索了整個數組，并且該元素不存在。

有兩種方法可以實現此算法-迭代和遞歸。

這里不應該是關于時間和空間這兩個實現之間復雜的差異，雖然這不成立于所有語言。

三，二分法檢索算法代碼實現

迭代式

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

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;   // 如果中間元素是我們的目標元素，那么返回它的索引   if (arr[middleIndex] == elementToSearch) {    return middleIndex;   }    // 如果中間的元素比較小   // 將我們的指數指向中間+1，不考慮前半部分   else if (arr[middleIndex] < elementToSearch)    firstIndex = middleIndex + 1;     // 如果中間的元素更大    // 將我們的指數指向中間1，不考慮下半部分   else if (arr[middleIndex] > elementToSearch)    lastIndex = middleIndex - 1;   }  return -1; } /**  * 用于打印結果  * @param targetParameter  * @param index  */ public static void print(int targetParameter, int index) {  if (index == -1){   System.out.println(targetParameter + " 未找到");  }  else {   System.out.println(targetParameter + " 搜索結果為: " + index);  } } //測試一下 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); }}

輸出：

遞歸的

現在讓我們看一下遞歸實現：

遞歸方法的區別在于，一旦獲得新分區，我們便會調用方法本身。在迭代方法中，每當確定新分區時，我們都會修改第一個和最后一個元素，并在同一循環中重復該過程。

這里的另一個區別是遞歸調用被推入方法調用堆棧，并且每個遞歸調用占用一個空間單位。

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

public class SearchAlgorithms {  /**  *遞歸方法  * @param arr  * @param elementToSearch  * @return  */ public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) {   // 結束條件  if (lastElement >= firstElement) {   int mid = firstElement + (lastElement - firstElement) / 2;    // 如果中間元素是我們的目標元素，那么返回它的索引   if (arr[mid] == elementToSearch)    return mid;    // 如果中間元素大于目標元素   if (arr[mid] > elementToSearch)    return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);    return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);  }   return -1; } /**  * 用于打印結果  * @param targetParameter  * @param index  */ public static void print(int targetParameter, int index) {  if (index == -1){   System.out.println(targetParameter + " 未找到");  }  else {   System.out.println(targetParameter + " 搜索結果為: " + index);  } } //測試一下 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); }}

輸出：

四，以算法時間復雜度和空間復雜度總結算法。

時間復雜度

由于二進制搜索每次將其時間復雜度為O（log（N））時都會將數組分為兩半。此時間復雜度是線性搜索O（N）時間復雜度的顯著改進。

空間復雜度

此搜索僅需要一個空間單位即可存儲要搜索的元素。因此，其空間復雜度為O（1）。

如果二分法檢索是遞歸實現的，則需要將對該方法的調用存儲在堆棧中。在最壞的情況下，這可能需要O（log（N））空間。

它是大多數用于搜索的庫中最常用的搜索算法，二分法檢索樹也被許多存儲排序數據的數據結構所使用。

該Arrays.binarySearch方法中的Java API也實現了二進制搜索哦。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。