二分查找以及變種的總結

• 2020 年 3 月 12 日
• 筆記

一、初探二分查找

在面試的時候，尤其的一面，感覺讓你手寫二分，還真的不一定就能很快寫出來，所以在此總結分享給大家

1 二分查找是什麼？

」查找「顧名思義是在一堆數去找出我們需要的數，但是我們又想更快的找出我們需要找的數，所以我們就盡量的減少查找比較的次數。"二分"就是分成兩份來減少我們查找次數。

不急不急，假設我們這裡有十個數，我們來畫圖看看這是個什麼神操作。

從上圖我們知道，我們每次都和區間的中間項值進行比較，從而縮小查找區間的值。

2 時間複雜度？

這裡我們假設搜索區間一共n個數，第一次切分n/2,第二次n/4,第三次n/8……….n/2(k).這是一個等比數列，n/2^k=1,k=log2n,那麼時間複雜度為o(logn).

二 、二分的注意事項

1 二分查找要求數據必須是有序的。 2 二分查找依賴於數組隨機查找的特性，要求記憶體連續

三 、二分的實現

1 第一種小白寫法

int BinarySerach(vector<int>& nums,int n, int target) {      int left = 0, right = n-1;      while (left <= right) {          int mid = (left+right)/2;          if (nums[mid] == target) return mid;          else if (nums[mid] < target) left = mid + 1;          else right = mid-1;      }      return -1;  }  

面試官發話了

2 方法二優化版 如果right和left比較的時候，兩者之和可能溢出。那麼改進的方法是mid=left+(right-left)/2.還可以繼續優化，我們將除以2這種操作轉換為位運算mid=left+((right-left)>>1).

哪有這麼簡單的事兒，大多數的筆試面試中可能會出現下面的幾種情況。

四 、二分的各種變種

這裡主要是看看原始數組有重複數的情況。

1 查找第一個值等於給定值的情況(查找元素7) 思路

首先7與中間值a[4]比較，發現小於7，於是在5到9中繼續查找，中間a[7]=7,但是這個數7不是第一次出現的。那麼我們檢查這個值的前面是不是等於7，如果等於7，說明目前這個值不是第一次出現的7，此時更新rihgt=mid-1.ok我們看看程式碼

int BinarySerach(vector<int>& nums, int n,int target) {      int left = 0, right = n-1;      while (left <= right) {          int mid = left+((right-left)>>1);          if (nums[mid]>value)          {              right=mid-1;          } else if(nums[mid]<value)          {              left=mid+1;          }else          {              if((mid==0)||(nums[mid-1]!=value))              {                  return mid;              }else              {                  left=mid-1;              }          }      return -1;  }  

2 查找最後一個值等於給定值的情況

假設nums[mid]這個值已經是最後一個元素了，那麼它肯定是要找到最後一個值。如果nums[mid]的下一個不等於value，那說明nums[mid]就是我們需要找到最後一個等於給定值的值。

int BinarySerach(vector<int>& nums, int n,int target) {      int left = 0, right = n-1;      while (left <= right) {          int mid = left+((right-left)>>1);          if (nums[mid]>value)          {              right=mid-1;          } else if(nums[mid]<value)          {              left=mid+1;          }else          {              if((mid==n-1)||(nums[mid+1]!=value))              {                  return mid;              }else              {                  left=mid+1;              }          }      return -1;  }  

3 查找第一個大於等於給定值的情況

1 如果nums[mid]小於要查找的值，那麼我們需要查找在[mid+1,right]之間，所以此時更新為left=mid+1 2 如果nums[mid]大於給定值value,這個時候需要查看nums[mid]是不是我們需要找的第一個值大於等於給定值元素，如果nums[mid]前面沒有元素或者前面一個元素小於查找的值，那麼nums[mid]就是我們需要查找的值。相反 3 如果nums[mid-1]也是大於等於查找的值，那麼說明查找的元素在[left,mid-1]之間，所以我們需要將right更新為mid-1

int BinarySerach(vector<int>& nums, int n,int target) {      int left = 0, right = n-1;      while (left <= right) {          int mid = left+((right-left)>>1);          if (nums[mid]>=value)          {              if(mid==0||nums[mid-1]<value)              {                  return mid;              }else              {                  right=mid-1;              }          }else          {              left=mid+1;          }      return -1;  }  

4 查找最後一個小於等於給定值的情況

1 如果nums[mid]小於查找的值，那麼需要查找的值肯定在[mid+1,right]之間，所以我們需要更新left=mid+1 2 如果nums[mid]大於等於給定的value，檢查nums[mid]是不是我們的第一個值大於等於給定值的元素

int BinarySerach(vector<int>& nums, int n,int target) {      int left = 0, right = n-1;      while (left <= right) {          int mid = left+((right-left)>>1);          if (nums[mid]>value)          {              right=mid-1;          }else          {              if(mid==n-1||(nums[mid+1]>value))              {                  return mid;              }else              {                  left=mid+1;              }          }      return -1;  }