1. 二分算法的几种形式与框架

1.1 普通查找

普通查找即在一个有序数组中只要找到该元素即可，比如1 2 2 2 2 2 3，使用二分查找算法查找到的是中间的2，找到即返回下标

  1. 左闭右开 ```java public static int binary_search(int nums[], int target) {
    1.  if (nums == null || nums.length == 0)
    2.      return -1;
    3.  int left = 0, right = nums.length;
    4.  while (left < right) {//注意点1
    5.      int mid = left + (right - left) / 2;
    6.      if (nums[mid] == target)
    7.          return mid;
    8.      else if (nums[mid] < target)
    9.          left = mid + 1;
    10.      else if (nums[mid] > target)
    11.          right = mid;//注意点2
    12.  }
    13.  return -1;
    }
> **注意点1**：因为right的取值是nums.length，因此while循环处需要使用<号，而不是<=, 因为当left==right==nums.length;时，循环体中的下标就有可能越界；
> **注意点2**： 因为时左闭右开区间，因此当mid被访问之后，当访问mid左边的元素时应该是[left.mid-1], 由于是左闭右开区间，因此当right=mid时，即[left,mid), [left.mid-1]等价于[left,mid)

2. **左闭右闭**
```java
public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {//注意点1
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;//注意点2
        }
        return -1;
    }

注意点1： 因为right的取值是nums.length-1，因此while循环处需要使用<=号，此时当left==right==nums.length-1时，循环体中下标并不会越界； 注意点2：因为时左闭右闭区间，因此当mid被访问之后，当访问mid左边的元素时应该是[left.mid-1], 由于是左闭右闭区间，所以直接right=mid-1

1.2 最左查找

最左查找是找到目标元素在数组中出现的最靠左边的位置，比如1 2 2 2 3，此时需要找的就是最左边的2 这种情况下当找到一个元素和target元素相同时不能立即返回，而是需要减小right,继续往左寻找 记最左查找返回的下标为index, index的一种意义是数组中的元素比targer元素小/大的个数，比如例子中比2小的元素有1个1

  1. 左闭右开 ```java public static int binary_search(int nums[], int target) {

     if (nums == null || nums.length == 0)
     return -1;
 int left = 0, right = nums.length;
 while (left < right) {//注意点1
     int mid = left + (right - left) / 2;
     if (nums[mid] == target)
         right=mid;//注意点2
     else if (nums[mid] < target)
         left = mid + 1;
     else if (nums[mid] > target)
         right = mid;//注意点3
 }
 // target比nums数组中的所有数字都大或都小（target不存在）
 //先进行left范围的判断，防止后面数组访问越界
 if(left>=nums.length||nums[left]!=target)//注意点4
    return -1;
 return left;

    }


2. **左闭右闭**
```java
public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                right=mid-1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        // target比nums数组中的所有数字都大/小（target不存在）
        //先进行left范围的判断，防止后面数组访问越界
        if(left>=nums.length||nums[left]!=target)
           return -1;
        return left;

    }

 //升序
public int binary_search_left(int arr[],int target)
    {
        int left=0,right=arr.length-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(arr[mid]>target)
                right=mid-1;
            else if(arr[mid]<target)
                left=mid+1;
            else if(arr[mid]==target)
            {
                if(mid==0||arr[mid-1]!=target)
                    return mid;
                else
                    right=mid-1;
            }
        }
        return -1;
    }

//降序
//降序
public static int binary_search_left(int arr[],int target)
    {
        int left=0,right=arr.length-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(arr[mid]>target)
                left=mid+1;
            else if(arr[mid]<target)
                right=mid-1;
            else if(arr[mid]==target)
            {
                if(mid==0||arr[mid-1]!=target)
                    return mid;
                else
                    right=mid-1;
            }
        }
        return -1;
    }

1.3 最右查找

最左查找是找到目标元素在数组中出现的最靠右边的位置，比如1 2 2 2 3，此时需要找的就是最右边的2 这种情况下当找到一个元素和target元素相同时不能立即返回，而是需要增大left,继续往右寻找

  1. 左闭右开 ```java public static int binary_search(int nums[], int target) {

     if (nums == null || nums.length == 0)
     return -1;
 int left = 0, right = nums.length;
 while (left < right) {//注意点1
     int mid = left + (right - left) / 2;
     if (nums[mid] == target)
         left=mid+1;//注意点2
     else if (nums[mid] < target)
         left = mid + 1;
     else if (nums[mid] > target)
         right = mid;//注意点3
 }
 // target比nums数组中的所有数字都小/大（target不存在）
 //先进行right范围的判断，防止后面数组访问越界
 //因为right取不到，因此right<=0时，[left,right)即为空
 if(right<=0||nums[right-1]!=target)
    return -1;
 return right-1;//因为right取不到 所以返回right-1

    }


2. **左闭右闭**
```java
public static int binary_search(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                left=mid+1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        // target比nums数组中的所有数字都小/大（target不存在）
        //先进行right范围的判断，防止后面数组访问越界
        //因为right可以取到，因此right<0时，[left,right]即为空
        if(right<0||nums[right]!=target)
           return -1;
        return right;//right可以取到 返回right

    }

//升序
public int binary_search_right(int arr[],int target)
    {
        int left=0,right=arr.length-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(arr[mid]<target)
                left=mid+1;
            else if(arr[mid]>target)
                right=mid-1;
            else if(arr[mid]==target)
            {
                if(mid==arr.length-1||arr[mid+1]!=target)
                    return mid;
                else
                    left=mid+1;
            }
        }
        return -1;
    }

//降序
public static int binary_search_right(int arr[],int target)
    {
        int left=0,right=arr.length-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(arr[mid]>target)
                right=mid-1;
            else if(arr[mid]>target)
                left=mid+1;
            else if(arr[mid]==target)
            {
                if(mid==arr.length-1||arr[mid+1]!=target)
                    return mid;
                else
                    left=mid+1;
            }
        }
        return -1;
    }

1.4 下界

//[1,3,5,7,9]   4的下界是3
public static  int lower_bound(int arr[],int target) {

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

    }

//[9,7,5,3,1]   4的下界是5
public static  int lower_bound(int arr[],int target) {

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

    }

1.5 上界

//[1,3,5,7,9]   4的上界是5
public static  int upper_bound(int arr[],int target) {

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

//[9,7,5,3,1]   4的上界是3
public static  int upper_bound(int arr[],int target) {

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

2. 二分算法实战

704. 二分查找

图片.png

class Solution {
    public int search(int[] nums, int target) {
       if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length;
        while (left < right) {//注意点1
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;//注意点2
        }
        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

图片.png

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int a=binary_search_left(nums,target);
        int b=binary_search_right(nums,target);
        return new int[]{a,b};

    }
    public int binary_search_left(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                right=mid-1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        // target比nums数组中的所有数字都大/小（target不存在）
        //先进行left范围的判断，防止后面数组访问越界
        if(left>=nums.length||nums[left]!=target)
           return -1;
        return left;

    }
    public int binary_search_right(int nums[], int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                left=mid+1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid-1;
        }
        // target比nums数组中的所有数字都小/大（target不存在）
        //先进行right范围的判断，防止后面数组访问越界
        //因为right可以取到，因此right<0时，[left,right]即为空
        if(right<0||nums[right]!=target)
           return -1;
        return right;//right可以取到 返回right

    }

}

875. 爱吃香蕉的珂珂

图片.png

题目大意：一次只能吃一堆香蕉，比如k=4,当前堆香蕉数目是6，要吃两次，第一次吃4根，第二次吃2根； 如果当前香蕉数目较小，比如k=4,当前堆香蕉数目是6,只吃1次，吃完剩下的时间不再吃其他的堆的香蕉； 记录一个函数f(k), 该函数是根据当前的k得到所需要的吃香蕉时间，然后可以将这个时间和H进行比较，f(k)是一个单调递减函数（K 越大时间越短)

图片.png

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left=1,right=1000000000+1;
        //时间最长-->速度最慢-->1小时吃1根
        //时间最短-->速度最快-->1小时吃max(piles)根
        while(left<right)
        {
            int mid=(right-left)/2+left;
            if(f(piles,mid)==h)
                right=mid;
            else if(f(piles,mid)>h)
                left=mid+1;
            else if(f(piles,mid)<h)
                right=mid;
        }

        return left;

    }
    public int f(int[] piles,int k)
    {
        int hours=0;
        for(int pile:piles)
        {
           hours+=pile/k;//当前堆香蕉吃的时间
           if(pile%k!=0)//如果没吃完 下一次需要单独花1个小时来吃
            hours++;
        }
        return hours;
    }
}

1011. 在 D 天内送达包裹的能力

图片.png

构造一个函数f(x): 表示在载重量为x的情况下，需要的天数, f(x)单减少 left: 最小载重量应该是min(weights) right: 最大载重量应该是sum(weights) 最后right++ , 因为代码中使用的是左闭右开区间，右区间取不到 由于f(x)是一个单调递减函数，我们要的是最小的x, 因此是二分最左查找 其次为了加快算法执行效率，可以经while循环体中的if语句进行合并

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left=0,right=0;
        for(int weight:weights)
        {
            left=Math.max(left,weight);
            right+=weight;
        }
        right+=1;//右开区间 right+1取不到
        while(left<right)
        {
            int mid=(right-left)/2+left;
            // if(f(weights,mid)==days)
            //     right=mid;//最左边界搜索
            // else if(f(weights,mid)>days)
            //     left=mid+1;
            // else if(f(weights,mid)<days)
            //     right=mid;
             if(f(weights,mid)>days)
                left=mid+1;//最左边界搜索
            else
               right=mid;
        }
        return left;

    }
    public int f(int[] weights,int x)
    {
        int days=0;
        for(int i=0;i<weights.length;)
        {
            int cap=x;
            while(i<weights.length)
            {
                if(cap<weights[i])
                    break;
                cap-=weights[i];
                i++;
            }
            days++;
        }
        return days;
    }
}

图片.png