Note-二分法

二分法

在網上搜，能看見比較詳細的二分法的介紹，但是筆者還是想去梳理一下，因為想要真正了解二分法的代碼和二分法的原理是不一樣的。首先，看一個比較常用的二分法算法。

public int binarySearch(int nums[],int target){
        Arrays.sort(nums);
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]>target){
                right=mid-1;
            }
            else {
                left=mid+1;
            }
        }
        return left;
    }
           

我們主要從兩個邊界問題來考慮這個函數會怎麼樣:

• 如果nums的取值範圍在[a,b]，并且target值屬于[a,b]，但是target不等于nums中的任意元素。對于這種情況下，我們能夠得到binarySearch傳回一個index值，但是nums[index]并不對于target。

  如nums=[0,1,2,3,4,5,6,7,8] target=2.5

  輪次	left	right	mid
  1	8	4
  2	3	1
  3	2	3	2
  4	3	3	3
  5	3	2	2

  最終輸出的值為3，因為找不到target。

• 如果nums的取值範圍在[a,b]，并且target值不屬于[a,b]，則會出現超過數組的index

  如nums=[0,1,2,3,4,5,6,7,8] target=9

  輪次	left	right	mid
  1	8	4
  2	5	8	6
  3	7	8	7
  4	8	8	8
  5	9	8	8

  最終輸出的值是9，找不到index。

  這個方法我們再找最終輸出的index是否滿足要求，需要判斷index是否在nums數組範圍的同時判斷nums[index]是否對于target，這樣子就比較麻煩，是以需要改進一下算法

public int binarySearch(int nums[],int target){
        Arrays.sort(nums);
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]>target){
                right=mid;
            }
            else {
                left=mid+1;
            }
        }
        return left;
    }
           

該方法就不會越界，但是還是需要判斷nums[index]是否等于target。

• 那麼對于nums=[0,1,2,3,4,4,4,5,6,7]，target=4，并且我想得到最左邊的4的下标，我們怎麼改進算法呢？

  public int binarySearch(int nums[],int target){
          Arrays.sort(nums);
          int left=0,right=nums.length-1;
          while(left<right){
              int mid=(left+right)/2;
  			if(nums[mid]>=target){
                  right=mid;
              }
              else {
                  left=mid+1;
              }
          }
          return left;
      }
             

• 同理，我們想找到最右邊的4的下表，我們應該怎麼改進呢?

  可以思考一下，然後見下面的答案：

  public int binarySearch(int nums[],int target){
          Arrays.sort(nums);
          int left=0,right=nums.length-1;
          while(left<right){
              int mid=(left+right)/2+(left+right)%2;
              if(nums[mid]<=target){
                  left=mid;
              }
              else {
                  right=mid-1;
              }
          }
          return right;
      }
             

  注意這個mid是如何取值的，本質上也是相對于去最左邊值的對偶關系

• 那麼介紹完了二分法了之後，可以嘗試做一下leetcode題目

  https://leetcode-cn.com/problems/minimum-time-to-complete-trips/