【二分查找】演算法

二分查找

其實二分查找是一個很容易理解的演算法，其需要注意的一點就是細節-----邊界問題。

目錄：

簡介

例子

總結

簡介：

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。在這個有序序列中，給定一個目標值target，並尋找一個左邊界left，一個右邊界right，由此得出中間值mid=(left+right)/2。讓中間值與目標值比較，重複操作，逐漸縮小範圍，直到確認目標值target是否存在給定的序列中以及具體位置。

 

例子：

問題描述：

給定一個數組nums,一個目標值target，需要查找target是否存在數組nums中，如果存在，輸出target所在的下標，否則返回-1。

首先一般查找有如下限制條件：

  • 數組nums里的數字不重複
  • 數組默認為升序的

在這樣的條件，我們採用二分查找的思想呢，就可以舉出這樣的實例，比如nums=[1,2,3,5,6,8],target=5,那麼返回下標就是3.

具體思想實現呢，步驟如下：

  • 確定left=0，right=nums.length-1=5,那麼中間值mid=(0+5)/2=2（注意，不理解的話可以先往下看）
  • nums[mid]與target相比較,nums[mid]小於目標值，那麼範圍縮小為[mid+1,right],即[3，5]
  • 重複第一步，mid=(3+5)/2=4,則nums[mid]=6大於目標值，範圍再一次縮小為[left,mid-1],即[3,3]
  • 顯然可知，最終鎖定nums[3]=5=target,返回下標mid----3。

大致思想已經明確，我們需要不斷確認左右邊界，逐漸縮小範圍，最終才能達到我們想要的目的，但在這個過程中，有兩個小細節需要注意，且一定要弄清楚！

細節一：

首先我們為了確保每個值都要考慮到，於是我們選擇的邊界是左右均為閉區間[left,right],那麼我們確定後中間值mid時，nums[mid]已經參與與target的比較了，如果nums[mid]不等於target，那麼接下來的計算，mid這個下標就需要拋棄。當中間值小於目標值時，我們就把範圍鎖定後半部分[mid+1,right],此時，left=mid+1;同理，中間值大於目標值時，範圍就鎖定在[left,mid-1],此時right=mid-1;

細節二：

序列的長度為奇數是，中間值mid=(right+left)/2正好是一個整數，可以直接確定中間值，但是當序列的長度為偶數時，mid的計算值為非整數，眾所周知，序列的下標均為整數，那麼中間值又該如何確定呢？例如，mid=3.5,那中間值應該取nums[3]還是nums[4]呢？

事實證明，其實這一點，不用糾結，因為我們在縮小範圍的過程中，我們採用的都是閉區間，而且加上它升序的特點，我們拋棄掉的部分都是不符合要求的。所以並不存在漏掉某個元素的問題，不知道大家糾不糾結這一點，反正我有的時候腦子很😵，之前學習的時候，常因為這一點而頭疼二分查找。

那麼具體程式碼實現就如下所示：

 1 int binarySearch(int[] nums,int target){
 2     int left=0,right=nums.length-1;
 3     while(left<=right){//注意，左右閉區間
 4         int mid=(left+right)/2;
 5         if(nums[mid]==target){
 6             return mid;
 7         }
 8         else if(nums[mid]<target){
 9             left=mid+1;
10         }
11         else if(nums[mid]>target){
12             right=mid-1;
13         }
14     }
15     return -1;
16 }

 

這是一般查找，因為它有著很好的條件，比如數組是升序且不重複的，那麼如果沒有順序的時候怎麼查找（還能用二分查找嗎？這個我還沒學會（狗頭），先不管它了吧），但是改為「數組依舊為升序序列，但是存在重複數字，這個時候，存在的話，確定target所在的下標（最左邊的或者最右邊的），否則返回-1。

以確定最左邊下標為例，我們需要確定目標值所在的序列的下標範圍，這個時候返回最左邊的下標left即可。這樣的情況下如何解決呢？

假設nums=[1,2,3,3,3,3,5,8,10],target=3,則大致步驟如下：

  • left=0，right=8，mid=(0+8)/2=4,所以nums[4]=3=target,鎖定範圍為[left,mid],即[0,4](注意：因為我們要找的是最左邊下標，所以左側我們取得是閉區間，而右側取閉區間的原因是為了防止目標值在序列中沒有重複數字的情況下，我們因過度注意左側下標而把右側數據遺忘掉。即right=mid）
  • 鎖定[0,4]範圍之後，再一次確定mid=2,此時nums[2]=3=target,那麼範圍就變成了[0,2]
  • 重複以上操作，mid=1,而nums[1]=2不等於目標值3，那麼left=mid+1，則範圍變成[left,right],即[2,2]
  • 則返回目標值下標2

與一般查找相比，讓人有點困擾的地方就是這個左右區間的確定

具體程式碼實現如下：

 1 int binarySearch(int[] nums,int target){
 2     int left=0,right=nums.length-1;
 3     while(left<=right){
 4         int mid=(left+right)/2;
 5         if(nums[mid]>=target){
 6             right=mid;//注意
 7         }
 8         else if(nums[mid]<target){
 9             left=mid+1;
10         }
11     }
12     if(left==right){
13         return left;
14     }
15     else if(left>nums.length){//注意
16         return -1;
17     }
18 }

求取最右側下標與以上類似，感興趣的話可以試試！

總結：

其實二分查找思想很容易理解，其難點就在於邊界的細節上，當你要用這個演算法時，需要注意的點呢就以下幾種：

  1. 循環條件，無論是左開右閉，左閉右開，還是左右均閉，循環里的條件一定要注意，否則很容易漏掉某個數據
  2. 左右邊界的確定，與第一條相似，要確保捨棄的均不符合條件

 

 

 

 

Tags:

VirMach 便宜 VPS