快捷導(dǎo)航

Java 二分法檢索算法代碼實(shí)現(xiàn)詳解

更新時(shí)間：2020年01月12日 14:19:07 作者：失控的狗蛋~

這篇文章主要介紹了Java 二分法檢索算法代碼實(shí)現(xiàn)詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

一，二分法檢索算法介紹

二分法檢索（binary search）又稱(chēng)折半檢索，二分法檢索的基本思想是設(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);
 }
}

輸出：