【二分查找】演算法-有解無憂

二分查找

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

簡介

例子

總結

簡介：

二分查找也稱折半查找（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 }

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

總結：

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

回圈條件，無論是左開右閉，左閉右開，還是左右均閉，回圈里的條件一定要注意，否則很容易漏掉某個資料
左右邊界的確定，與第一條相似，要確保舍棄的均不符合條件

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/504440.html

標籤：其他

上一篇：DevStream 社區貢獻者英雄榜上線啦！

下一篇：SQLI-LABS(Less-5)