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/