二分查找法

https://blog.csdn.net/kexuanxiu1163/article/details/89838372?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.pc_relevant_aa&spm=1001.2101.3001.4242.1&utm_relevant_index=3

二分查找又称为折半查找，它是一种在有序数组中查找某个特定元素的搜索算法。从前面的描述中可以看出使用二分查找法有一个很重要的前提 - 有序数组。也就是只有针对排好序的数据我们才能使用二分查找法。

二分查找法怎么做呢？

二分查找法的时间复杂度为 O(logn)，这里我们没有把排序时间算进去，如果算上排序时间二分查找法的时间复杂度就为 O(nlogn)

二分查找的应用场景是多次查找，我们经过一次排序后，后面使用二分查找对数据进行多次查找

快速排序的时间复杂度为 O(n)？？？

用快速排序解决 Select K 的时间复杂度为 O(n) 级别。

通过上面的介绍，大家是不是感觉二分查找法很简单呢，但就是这么简单的一个算法，它从 1946 年提出到写出第一个没有 bug 的二分查找法中间用了将近 16 年。你可会说真的假的，看着也不难呀。别急，在后续的章节中我们会对这个算法进行更深入的介绍，大家就会了解到这个算法容易出错的点了。

二分查找法的递归写法

思路：
找到数组的中间值 arr[mid]，和 target 进行对比
1. 等于 =》直接返回 mid
2. 小于 =》在右半块数组中查找 l = mid + 1
3. 大于 =》在左板块数组中查找 r = mid - 1

Java 版本如下：

public class BinarySearch {
    private BinarySearch() {}
    public static <E extends Comparable<E>> int search(E[] data, E target) {
        // 在区间 [0, data.length-1] 中查找 target
        return search(data, 0, data.length - 1, target);
    }
    private static <E extends Comparable<E>> int search(E[] data, int l, int r, E target) {
        // l > r 表明这个数组是一个空数组
        if (l > r) return -1;
        // 这样计算是为了避免整型溢出
        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) == 0) return mid;
        if (data[mid].compareTo(target) < 0) return search(data, mid + 1, r, target);
        return search(data, l, mid - 1, target);
    }
}

JS 版本如下：

function search1(nums, l, r, target) {
    if (l > r) return -1;
    const mid = Math.floor(l + (r - l) / 2);
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) return search1(nums, mid + 1, r, target);
    return search1(nums, l, mid - 1, target);
}

二分查找法的非递归写法

Java 版本：

public class BinarySearch {
    private BinarySearch2() {}
    private static <E extends Comparable<E>> int search(E[] data, E target) {
        // r 的值取数组长度减一，这是因为循环不变量是在 [l, r] 这个区间内查找符合条件的值，出了这个取件就找不到了
        int l = 0, r = data.length - 1;
        // l <= r 的时候说明数组中还存在可查找的元素，就需要继续查找
        while (l <= r) {
            // 获取数组的中间索引
            int mid = l + (r - l) / 2;
            // 如果当前查找的值和 target 相等，就说明找到了要找的值，直接返回 mid
            if (data[mid].compareTo(target) == 0) return mid;
            // 如果当前查找的中间元素小于 target，则在数组的右半部分查找 target
            if (data[mid].compareTo(target) < 0) l = mid + 1;
            // 如果当前查找的中间元素大于 target，则在数组的左半部分查找 target
            else r = mid - 1;
        }
        return -1;
    }
}

JS 版本：

var search = function(nums, target) {
    let l = 0, r = nums.length - 1;

    while (l <= r) {
        const mid = Math.floor(l + (r - l) / 2);
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
};

作业：Select K 的非递归写法todo

换个定义实现二分查找法

修改循环不变量定义实现二分查找法

public class BinarySearch3 {
    private BinarySearch3() {}
    public static <E extends Comparable<E>> int search(E[] data, E target) {
        /*
        * 思路：
        * 使用二分查找法在区间 [l, r) 中查找 target
        * 获取中间索引 mid
        *  1.如果当前mid的值小于target，查找mid的右边数据
        *  2.如果当前mid的值大于target，查找mid的左边的数据
        *  3.如果当前mid的值等于target，直接返回
        *  4.找不到的话返回-1*/
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) == 0) return mid;
            if (data[mid].compareTo(target) < 0) l = mid + 1; // 继续在 data[mid+1, r) 范围里寻找解
            else r = mid; // 注意这里不是 mid-1 ,因为我们需要在 data[l, mid) 范围里寻找解，如果 r = mid - 1，就不包含这个值了
        }
        return -1;
    }
}

1-7 作业：换个定义实现算法todo

二分查找法的变种：upper

前面我们简要讲了下二分查找，下面我们来举一个比较常见的例子，查找大于 target 的最小值所在的索引。
思路：
搜索范围是 [l, r]，r = arr.length；你可能会问为啥 r 的初始值为数组的长度而不是数组长度减 1 呢？这是因为数组最后的那个值可能是和要找的 target 是相等的，这时要找大于 target 的最小值就要往它右边找

public class BinarySearch3 {
    private BinarySearch3() {}
    private static <E extends Comparable<E>> int upper(E[] data, E target) {
        /**
         * 需求：
         * 在一个数组中查找一个大于target的最小值
         *
         * 思路：
         * 不使用二分查找
         * 1. 将数组从小到大排序
         * 2. 直接遍历数组，第一个比target大的值就是要找的值，如果数组中的第一个值大于 target 就返回 0 或者最后一个值 <= target直接返回-1，遍历到最后也找不到也返回-1
         * 使用二分查找法的非递归方式
         * 1. 我们需要在 [l, r] 中查找目标元素，就需要确认两个值的初始值
         * 2. l = 0， r = data.length; ? data = [1, 2, 3, 4, 5]; target = 3;
         * 3. 获取mid的值
         *      mid位置的值和target的值进行对比
         *          小于或等于target mid右边的就是要找的值 l = mid + 1
         *          大于target r = mid;
         */

        int l = 0, r = data.length;
        //  ***** 错误分析：写错了，不是 l <= r，应该是 l < r，因为循环不变量是在区间 [l, r] 中查找，l 等于 r 后，说明一定找到了
//        while (l <= r) {
        while (l < r) {
            int mid = l + (r - l) / 2;
            // ***** 错误分析：这里应该将小于或者等于的情况合并
//            if (data[mid] == target) return mid + 1 < data.length ? mid + 1 : -1;
//            if (data[mid] < target) l = mid + 1;
//            else r = mid;

            if (data[mid].compareTo(target) <= 0) l = mid + 1;
            else r = mid; // 这里不需要减 1，因为 mid 所在的位置可能就是要找的值
        }
//        ***** 错误分析：这里不应该返回 -1，当 l 和 r 相等的时候说明找到了想找的元素，这个时候随便返回l或者r都是可以的
//        return -1;
        return  l;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 1, 3, 3, 5, 5};
        for (int i = 0; i<= 6; i++)
            System.out.print(BinarySearch3.upper(arr, i) + " ");
        System.out.println();
    }
}

二分查找法的变种：ceil

我们使用二分查找实现下这个问题：

在给出的输出中查找指定的元素，如果当前数组中存在和要找的元素相等的元素就返回相等元素的最大索引；如果当前数组中不存在和要找的元素相等的元素就返回大于要找的这个元素的最小值所在的索引。

思路：
我们先找到大于 target 的最小值，因为数组是升序的，所以就看大于 target 的最小值所在的位置的前面那个元素是否等于 target ，如果等于，这个值的索引就是结果，如果不等于，则直接返回大于 target 的最小值的索引即可。

public class BinarySearch3 {
    private BinarySearch3() {}
    private static <E extends Comparable<E>> int ceil(E[] data, E target) {
        /*
        * 功能：
        * 1. 如果数组中存在要找的元素，返回最大想等元素的最大索引
        * 2. 如果数组中不存在要找的元素，返回 upper
        * 思路：
        * 1.先找到 upper
        *   1. 在区间 [l, r] 找符合的数据，当 l==r 的时候就找到了
        *   2. 获取 mid 处的值，看看和 target 进行对比
        *       1. 大于 l = mid
        *       2. 小于或等于 r = mid + 1
        * 2. 判断 upper - 1 的和这个值是否相等
        *   1. 相等， upper - 1就是要找的索引
        *   2. 不等 upper就是要找的索引*/
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) <= 0) l = mid + 1;
            else r = mid;
        }
        // l-1 >= 0 判断要查找索引的合法性
        if (l-1>=0 && data[l-1].compareTo(target) == 0) return l - 1;
        return l;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 1, 3, 3, 5, 5};
        for (int i = 0; i<= 6; i++)
            System.out.print(BinarySearch3.ceil(arr, i) + " ");
        System.out.println();
    }
}

二分查找法的变种：lower_ceil

实现 lower_ceil，如果数组中存在要查找的元素，返回最小索引；如果数组中不存在要查找的元素，返回 upper。

public class BinarySearch3 {
    private BinarySearch3() {}
    private static <E extends Comparable<E>> int lower_ceil(E[] data, E target) {
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) < 0) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static void main(String[] args) {
        Integer[] arr = {1, 1, 3, 3, 5, 5};
        System.out.print(BinarySearch3.lower_ceil(arr, 10) + " ");
    }
}

我自己的实现方式：
思路：当找到相等元素后，就看看左边的元素是否也和target相等，如果相等，就继续看左边的元素，直到不等为止。

function lowerCeil(arr, target) {
    let l = 0,
        r = arr.length;
    while (l < r) {
        let mid = Math.floor(l + (r - l) / 2);
        if (arr[mid] == target) {
            while (mid >= 0 && arr[mid - 1] == target) {
                mid -= 1;
            }
            return mid;
        } else if (arr[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l;
}
const arr = [ 0, 1, 1, 1, 1, 2, 2, 2, 12 ],
    target = 1;
console.log(lowerCeil(arr, target));

二分查找法的变种：lower

查找小于 target 的最大值

通过之前的学习你可能很快写出下面的代码：

function lower(arr, target) {
  let l = -1, r = arr.length - 1;
  while (l < r) {
    let mid = Math.floor(l + (r - l) / 2)
    if (arr[mid] < target) l = mid;
    else r = mid - 1;
  }
  return l;
}

看着好像没问题，但当我们实际测试的时候发现程序卡死了：

function lower(arr, target) {
  let l = -1, r = arr.length - 1;
  while (l < r) {
    let mid = Math.floor(l + (r - l) / 2)
    if (arr[mid] < target) l = mid;
    else r = mid - 1;
  }
  return l;
}

const arr = [1, 2, 3, 4], target = 10;
console.log(lower(arr, target));

下面我们来调试代码看看，如果你不知道怎么在 vscode 中调试代码，可以看下下面这张动图，这里不再做详细介绍：

我们调试下上面的代码就会看出 l 的值为 2 的时候就不再变化了，导致程序进入了死循环：

这是因为当 l 等于 2 的时候，r 的值为 3，此时计算出来的 mid 的值为 2，arr[2]<target 成立，会走到 if 语句中再次给 l 赋值为 2 ，如此往复，l < r 一直成立。简单来说就是当 l 和 r 相邻的时候，由于我们使用的是向下取整数，导致 l 一直没有发生变化：

const mid = Math.floor(l + (r - l) / 2) =>
// l 和 r 相邻时 (r - l) / 2 = 0.5
const mid = Math.floor(l + 0.5) =>
const mid = l;

解决办法也很简单 const mid = Math.floor(l + (r - l + 1) / 2); 将计算结果上取整即可。

const mid = Math.floor(l + (r - l + 1) / 2); =>
// 如果 l 和 r 相邻，它们的差值为 1
const mid = Math.floor(l + (1 + 1) / 2); =>
const mid = Math.floor(l + 1); =>
mid = l + 1;

这样的话 mid 的值一定会变，在代码中 l = mid 所以 l 的值也一定会变。通过上面的学习，下面我们就可以写出正确的代码了：

Java版本：

private static <E extends Comparable<E>> int lower(E[] data, E target) {
    /*
        * 需求：
        * 查找小于 target 的最大值
        * 思路：
        * 1. 获取 mid 的值，并和 target 进行对比
        *   1. 小于target
        *       l = mid + 1;
        *   2. 大于等于target
        *       r = mid
        * */
    int l = -1, r = data.length - 1;
    // 在 data[l, r] 中寻找解，当 l 碰到 r，就说明只剩一个元素了，这个元素一定是解
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (data[mid].compareTo(target) < 0) l = mid;
        else r = mid - 1;
    }
    return l;
}

JS 版本：

function lower(arr, target) {
    let l = -1,
        r = arr.length - 1;
    while (l < r) {
        const mid = Math.floor(l + (r - l + 1) / 2);
        if (arr[mid] < target) l = mid;
        else r = mid - 1;
    }
    return l;
}

总结：在我们使用二分查找时一定要注意 l = mid 这种情况。

作业：二分查找法的变种：lower_floor 和 upper_floor

实现 lower_floor

lower_floor 方法要实现的功能：如果数组中存在要查找的元素，返回等于这个值的最小索引；如果数组中不存在要查找的元素，返回 lower 也就是小于 target 的最大值的索引。

思路：
上面我们实现的 lower 方法实现的是查找小于 target 的最大值索引，那么这个 lower 值的右边的元素就有可能是等于 target 的值。如果是的话就返回 lower 值加一，如果不是就返回 lower 值。

Java 版本代码如下：

public static <E extends Comparable<E>> int lowerFloor(E[] data, E target) {
    int l = -1, r = data.length - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (data[mid].compareTo(target) < 0) l = mid;
        else r = mid - 1;
    }
    if (l + 1 < data.length && data[l + 1].compareTo(target) == 0) return l + 1;
    return l;
}

JS 版本代码如下：

function lowerFloor(arr, target) {
    let l = -1,
        r = arr.length - 1;
    while (l < r) {
        const mid = Math.floor(l + (r - l + 1) / 2);
        if (arr[mid] < target) l = mid;
        else r = mid - 1;
    }
    if (l + 1 < arr.length && arr[l + 1] == target) return l + 1;
    return l;
}

实现 upper_floor

upper_floor 方法要实现的功能：如果数组中存在要查找的元素，返回最大索引；如果数组中不存在要查找的元素，返回 lower 也就是小于 target 的最大值的索引。

思路：通过对上面的分析，我们可以得出实际我们求的是 <= target 的最大索引，而 lower 求解的是小于 target 的最大索引，我们只需要在判断小于的时候加上等于就行了。

Java 版本代码如下：

public static <E extends Comparable<E>> int upperFloor(E[] data, E target) {
    int l = -1, r = data.length - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (data[mid].compareTo(target) <= 0) l = mid;
        else r = mid - 1;
    }
    return l;
}

JS 版本代码如下：

function upperFloor(arr, target) {
    let l = -1,
        r = arr.length - 1;
    while (l < r) {
        const mid = Math.floor(l + (r - l + 1) / 2);
        if (arr[mid] <= target) l = mid;
        else r = mid - 1;
    }
    return l;
}

二分查找法总结：二分查找模板

二分查找法的模板如下，? 表示需要根据实际情况实现的代码：

let l = ?, r = ?;
while (l < r) {
    let mid = ?;
  if (data[mid] ? target)?
  else ?
}
return l;

细心的朋友可能已经看出，上面给出的模板似乎只能实现前面我们讲的二分查找法的变种问题，似乎不适合确定某个元素是否存在。

需求：用求解 >= target 的最小值的思路实现二分查找法；
思路：

Java 版本：

public static <E extends Comparable<E>> int search2(E[] data, E target) {
    int l = 0, r = data.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) < 0) l = mid + 1;
        else r = mid;
    }
    if (l < data.length && data[l].compareTo(target) == 0) return l;
    return -1;
}

JS 版本：

function search(arr, target) {
    let l = 0,
        r = arr.length - 1;
    while (l < r) {
        const mid = Math.floor(l + (r - l) / 2);
        if (arr[mid] < target) l = mid + 1;
        else r = mid;
    }
  // 如果 arr[l] == target，则返回索引 l，否则返回 -1。
  // 求解 >= target 的最小值索引，结果可能是 data.length，不是合法索引，所以我们需要对 l 的合法性进行判断
    if (l < arr.length && arr[l] === target) return l;
    return -1;
}

3-5 更多二分查找相关问题

练习题

1. Pow(x, n)-50

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。



示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25


提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

十进制怎么转二进制？分为十进制值整数转二进制和十进制小数转二进制。我们先来说十进制整数怎么转二进制。它的转换法则为：除2取余，逆序排列。

2. x 的平方根-69

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。



示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。


提示：

0 <= x <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var mySqrt = function(x) {
    let l = 0, r = x;
    while (l < r) {
        const mid = Math.floor(l + (r - l) / 2) + 1;
          // 这里没有使用 mid * mid > x 是为了防止得到的数字溢出
          // mid > x / mid 表明中间的数字相乘大于 x ,此时需要缩小查找的范围，因为我们的范围从小到大排好序的，所以我们需要将右指针移动到 mid 的前面一位，即 r = mid - 1;
        if (mid > x / mid) r = mid - 1;
        else l = mid;
    }
      // 
    return l;
};

3. 二分查找-704

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1


提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var search = function(nums, target) {
  // 如果 nums 没有值或者数组长度为空，直接返回 -1
  if (!nums || !nums.length) return -1;
  // l 为数组第 0 个索引，r 为数组最后一个索引
    let l = 0, r = nums.length - 1;
  // 在区间 [l, r] 上查找符合要求的索引
  while (l <= r) {
    // 获取中间元素的下标，这里我们需要思考下获取中间索引时为什么使用 l + (r - l) / 2 ？直接使用 (l + r) / 2 不就行了吗？这是为了防止 l + r 溢出，也就是超出 Number 类型有效范围
      const mid = Math.floor(l + (r - l) / 2);
    // 如果中间元素的值就是要找的值，直接返回这个值的下标
    if (nums[mid] == target) return mid;
    // 如果中间元素的值小于 target , 就缩小查找范围，在数组的右半部分查找
    else if (nums[mid] < target) l = mid + 1;
    // 如果中间元素的值大于 target , 就缩小查找范围，在数组的左半部分查找
    else r = mid - 1;
  }
  // 没有找到的话直接返回 -1
  return -1;
};

4. 珂珂吃香蕉-875

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。



示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30
示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23


提示：

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/koko-eating-bananas
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS 版本：

var minEatingSpeed = function (piles, h) {
    let l = 1,
        r = Math.max(...piles);
    while (l < r) {
        const mid = Math.floor(l + (r - l) / 2);
        if (eatingTime(piles, mid) <= h) r = mid;
        else l = mid + 1;
    }
    return l;
};

function eatingTime(piles, k) {
    let res = 0;
    piles.forEach((pile) => {
        res += Math.ceil(pile / k);
    });
    return res;
}

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

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。



示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 
示例 2：

输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：

输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1


提示：

1 <= days <= weights.length <= 5 * 104
1 <= weights[i] <= 500

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var shipWithinDays = function(weights, days) {
  let l = Math.max(...weights), r = weights.reduce((sum, cur) => sum += cur);
  while (l < r) {
    const mid = Math.floor(l + (r - l) / 2);
    if (getDays(weights, mid) <= days) r = mid;
    else l = mid + 1;
  }
  return l;
};

function getDays(weights, k) {
  let cur = 0, res = 0;
  weights.forEach(weight => {
    if (cur + weight <= k) cur += weight;
    else {
      cur = weight;
      res++;
    }
  })
  return ++res;
}

6. 两数之和 II - 输入有序数组-167

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。


示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。


提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？


示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：

输入：nums = [], target = 0
输出：[-1,-1]


提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

8. 完全二叉树的节点个数-222

9. 最长递增子序列-300

10. 按权重随机选择-528