Java 二分法檢索算法代碼實現詳解

 更新時間:2020-01-12 19:00:29   作者:佚名   我要評論(0)

一,二分法檢索算法介紹


二分法檢索(binary search)又稱折半檢索,二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組(array)中。是最常用的搜索

一,二分法檢索算法介紹

二分法檢索(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也實現了二進制搜索哦。

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

您可能感興趣的文章:

  • java 二分法算法的實例

相關文章

  • Java 二分法檢索算法代碼實現詳解

    Java 二分法檢索算法代碼實現詳解

    一,二分法檢索算法介紹 二分法檢索(binary search)又稱折半檢索,二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組(array)中。是最常用的搜索
    2020-01-12
  • Linux下PHP+Apache的26個必知的安全設置

    Linux下PHP+Apache的26個必知的安全設置

    PHP是一種開源服務器端腳本語言,應用很廣泛。Apache web服務器提供了這種便利:通過HTTP或HTTPS協議,訪問文件和內容。配置不當的服務器端腳本語言會帶來各種各樣
    2020-01-12
  • tensorflow的計算圖總結

    tensorflow的計算圖總結

    計算圖 在 TensorFlow 中用計算圖來表示計算任務。 計算圖,是一種有向圖,用來定義計算的結構,實際上就是一系列的函數的組合。 用圖的方式,用戶通過用一些簡單
    2020-01-12
  • Python3.x+迅雷x 自動下載高分電影的實現方法

    Python3.x+迅雷x 自動下載高分電影的實現方法

    快要過年了,大家都在忙些什么呢?一到年底公司各種搶票,備年貨,被這過年的氣氛一烘,都歸心似箭,哪還有心思上班啊。歸心似箭=產出低下=一行代碼十個錯=無聊。于
    2020-01-12
  • 在微信小程序中渲染HTML內容3種解決方案及分析與問題解決

    在微信小程序中渲染HTML內容3種解決方案及分析與問題解決

    大部分Web應用的富文本內容都是以HTML字符串的形式存儲的,通過HTML文檔去展示HTML內容自然沒有問題。但是,在微信小程序(下文簡稱為「小程序」)中,應當如何渲
    2020-01-12
  • ES2020 新特性(種草)

    ES2020 新特性(種草)

    這幾年,Ecma TC39一年一次更新 ecmascript 規范標準,截止目前,以下特性已進入 finished 狀態,F在帶大家體驗種草 ES2020 新特性。 一:Promise.allSettled
    2020-01-12
  • Python 實現遞歸法解決迷宮問題的示例代碼

    Python 實現遞歸法解決迷宮問題的示例代碼

    迷宮問題 問題描述: 迷宮可用方陣 [m, n] 表示,0 表示可通過,1 表示不能通過。若要求左上角 (0, 0) 進入,設計算法尋求一條能從右下角 (m-1, n-1) 出去的路徑。
    2020-01-12
  • html2canvas屬性和使用方法以及如何使用html2canvas將HTML內容寫入Canvas生成圖片

    html2canvas屬性和使用方法以及如何使用html2canvas將HTML內容寫入Canvas生成圖片

    如何使用JS截取HTML頁面為圖片呢,下面為大家介紹一款JS截圖插件html2canvas.js html2canvas.js 能夠實現在用戶瀏覽器端直接對整個或部分頁面進行截屏。 html2can
    2020-01-12
  • golang并發編程的實現

    golang并發編程的實現

    go main函數的執行本身就是一個協程,當使用go關鍵字的時候,就會創建一個新的協程 channel channel 管道,用于在多個協程之間傳遞信號 無緩存管道 當對無
    2020-01-12
  • python opencv實現信用卡的數字識別

    python opencv實現信用卡的數字識別

    本項目利用python以及opencv實現信用卡的數字識別 前期準備 導入工具包 定義功能函數 模板圖像處理 讀取模板圖像 cv2.imread(img) 灰度化處理 cv2
    2020-01-12

最新評論

双色球基本走势图200