1. 定义

wiki：是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半

2. 常见问题

  1. 集合中搜索值为target的位置
  2. 集合中搜索值为target的左边界
  3. 集合中搜索值为target的右边界
  4. 集合中搜索值大于target的最后一个值的下标

  5. 集合中搜索值小于target的最后一个值的下标

    3. 二分搜索法要点

    3.1 搜索范围定义

    以常见问题1举例

    1. public static int findTargetValue(int[] arr,int target) {
    2.      int left = 0;
    3.      int right = arr.length-1;
    4.      while(left <= right) {
    5.          int mid = left + (right - left)/2;
    6.          if(arr[mid] == target) {
    7.              return mid;
    8.          } else if(arr[mid] > target) {
    9.              right = mid - 1;
    10.          } else if(arr[mid] < target) {
    11.              left = mid + 1;
    12.          }
    13.      }
    14.      return -1;
    15.  }

    可以看到left初始化为0，right初始化为arr.length-1，它代表着我们首次的搜索范围，即一个闭区间[left,right]，循环何时结束呢，当left>right时，即当搜索区间为[right+1,right]时，区间为无效区间，那么循环也就停止了，不论多少次循环我们只要记得如果是这种写法，那么我们每次的搜索区间都是一个闭区间
    接下来我们看下搜索区间为左闭右开的写法

    1. public static int findTargetValue2(int[] arr,int target) {
    2.      int left = 0;
    3.      int right = arr.length;
    4.      while(left < right) {
    5.          int mid = left + (right - left) / 2;
    6.          if(arr[mid] == target) {
    7.              return mid;
    8.          } else if(arr[mid] > target) {
    9.              right = mid;
    10.          } else if(arr[mid] < target) {
    11.              left = mid + 1;
    12.          }
    13.      }
    14.      return -1;
    15.  }

    这里与上面左闭右闭的写法不同的在于初始化right=arr.length，这个下标值是有效下标值加1，因此初始化的搜索区间为[left,right)，之后每轮的搜索区间虽然搜索的范围在减小，但是依然保持左闭右开区间，这里当arr[mid] > target时更新右边界为mid，因为我们的搜索区间为左闭右开，那么下次搜索区间就是[left,mid)，mid的值不会被再次取到。搜索结束时left=right，此时搜索区间为[left,left)，区间有效长度为0，搜索结束
    个人更加习惯左闭右闭的写法，之后的代码也会以左闭右闭的搜索区间为基础展示

    3.2 目标值与集合中值的范围关系

    假设集合中值范围为(x,n)，那么目标值与集合中值的范围关系可能有如下三种

  6. 在集合范围之外，即小于集合中的最小值或大于集合中值的最大值

  7. 在集合范围内但集合中不存在目标值
  8. 在集合范围内且集合中存在目标值

    4. 常见问题解答

    已经展示了如何在有序集合中搜索固定值的写法，接下来我们将展示其他几个常见问题的解法

  • 寻找目标值的左边界

    1. public static int findTargetLeftBorder(int[] arr,int target) {
    2.       int left = 0;
    3.       int right = arr.length-1;
    4.       int pre = -2;
    5.       while(left <= right) {
    6.           int mid = left + (right - left) / 2;
    7.           if(arr[mid] >= target) {
    8.               pre = mid;
    9.               right = mid -1;
    10.           } else {
    11.               left = mid + 1;
    12.           }
    13.       }
    14.       return pre;
    15.   }

    寻找目标值的左边界，即在寻找到目标值后不会跳出循环，而是继续向左搜索，可以想象是右边界不断向左缩进的过程，当arr[mid] >= target时，我们需要做的动作都是右边界向左边缩进。这里为什么是需要一个pre呢，因为当循环结束时right值肯定不等于mid，因为right = mid -1，所以我们需要一个pre记录边界下标，如果集合内存在该值，pre的值就是左边界的下标

  • 寻找目标值的右边界

    1. public static int findTargetRightBorder(int[] arr,int target) {
    2.       int left = 0;
    3.       int right = arr.length-1;
    4.       int pre = -2;
    5.       while(left <= right) {
    6.           int mid = left + (right - left) / 2;
    7.           if(arr[mid] <= target) {
    8.               pre = mid;
    9.               left = mid + 1;
    10.           } else {
    11.               right = mid - 1;
    12.           }
    13.       }
    14.       return pre;
    15.   }

    寻找右边界即在找到目标值时继续向右搜索，这里是左搜索边界不断向右移动的过程，当arr[mid] <= target时，移动左边界继续向右寻找。同寻找左边界一样，如果集合存在目标值，那么pre的值就是目标值的右边界

  • 寻找集合中小于目标值的最后一个值的下标

    1. // 有序集合：int[] arr = {1,2,2,4,6,9,10,12}，寻找小于3的最后一个值的下标，
    2. // 这里应该返回2，因为下标为2的值为2，它是最后一个小于3的值
    3. public static int findLastLessThanTarget(int[] arr,int target) {
    4.       int left = 0;
    5.       int right  = arr.length-1;
    6.       int pre = -2;
    7.       while(left <= right) {
    8.           int mid = left + (right - left) / 2;
    9.           if(arr[mid] < target) {
    10.               pre = mid;
    11.               left = mid + 1;
    12.           } else {
    13.               right = mid-1;
    14.           }
    15.       }
    16.       return pre;
    17.   }

  • 寻找集合中大于目标值的最后一个值的下标

    1. // 有序集合：int[] arr = {1,2,2,4,6,9,10,12}，寻找大于8的最后一个值的下标，
    2. // 这里应该返回5，因为下标为5的值为9，它是最后一个大于8的值
    3. public static int findLastBigThanTarget(int[] arr,int target) {
    4.       int left = 0;
    5.       int right  = arr.length-1;
    6.       int pre = -2;
    7.       while(left <= right) {
    8.           int mid = left + (right - left) / 2;
    9.           if(arr[mid] > target) {
    10.               pre = mid;
    11.               right = mid -1;
    12.           } else {
    13.               left = mid + 1;
    14.           }
    15.       }
    16.       return pre;
    17.   }

    5. 题目

  1. 分隔绳子

给定一个整数数组 ribbons 和一个整数 k，数组每项 ribbons[i] 表示第 i 条绳子的长度。对于每条绳子，你可以将任意切割成一系列长度为正整数的部分，或者选择不进行切割。

例如，如果给你一条长度为 4 的绳子，你可以：

保持绳子的长度为 4 不变；
切割成一条长度为 3 和一条长度为 1 的绳子；
切割成两条长度为 2 的绳子；
切割成一条长度为 2 和两条长度为 1 的绳子；
切割成四条长度为 1 的绳子。
你的任务是最终得到 k 条完全一样的绳子，他们的长度均为相同的正整数。如果绳子切割后有剩余，你可以直接舍弃掉多余的部分。

对于这 k 根绳子，返回你能得到的绳子最大长度；如果你无法得到 k 根相同长度的绳子，返回 0。

示例 1:

输入: ribbons = [9,7,5], k = 3
输出: 5
解释:

  • 把第一条绳子切成两部分，一条长度为 5，一条长度为 4；
  • 把第二条绳子切成两部分，一条长度为 5，一条长度为 2；
  • 第三条绳子不进行切割；
    现在，你得到了 3 条长度为 5 的绳子。
    示例 2:

输入: ribbons = [7,5,9], k = 4
输出: 4
解释:

  • 把第一条绳子切成两部分，一条长度为 4，一条长度为 3；
  • 把第二条绳子切成两部分，一条长度为 4，一条长度为 1；
  • 把第二条绳子切成三部分，一条长度为 4，一条长度为 4，还有一条长度为 1；
    现在，你得到了 4 条长度为 4 的绳子。
    示例 3:

输入: ribbons = [5,7,9], k = 22
输出: 0
解释: 由于绳子长度需要为正整数，你无法得到 22 条长度相同的绳子。

提示:

1 <= ribbons.length <= 105
1 <= ribbons[i] <= 105
1 <= k <= 109

  1. public static int maxLength(int[] ribbons, int k) {
  2.         int max = Integer.MIN_VALUE;
  3.         for(int i = 0;i < ribbons.length;i++) {
  4.             max = Math.max(max,ribbons[i]);
  5.         }
  6.         int left = 1;
  7.         int right = max;
  8.         int pre = -1;
  9.         while(left <= right) {
  10.             int mid = left + (right - left) / 2;
  11.             int count = getSplitNum(ribbons,mid);
  12.             if(count >= k) {
  13.                 pre = mid;
  14.                 left = mid + 1;
  15.             } else {
  16.                 right = mid -1;
  17.             }
  18.         }
  19.         return pre == -1?0:pre;
  21.     }
  23.     private static int getSplitNum(int[] ribbons,int mid) {
  24.         int count = 0;
  25.         for(int len:ribbons) {
  26.             count += len / mid;
  27.         }
  28.         return count;
  29.     }
  31.     public static void main(String[] args) {
  32.         int[] ribbons = new int[]{1,1,1};
  33.         System.out.println(maxLength(ribbons,3));
  34.     }