前言

二分查找算法是典型的「减治思想」的应用，我们使用二分查找将待搜索的区间逐渐缩小，以达到「缩减问题规模」的目的；
掌握二分查找的两种思路重点：
- 思路 1：在循环体内部查找元素：while (left <= right)；
- 思路 2：在循环体内部排除元素：while (left < right)。
全部使用左闭右闭区间，不建议使用左闭右开区间，反而使得问题变得复杂；

不建议背模板，每一步都要清楚为什么这样写，不要跳步，更不能想当然。

思路 1：在循环体内部查找元素（解决简单问题时有用）

class Solution {
  public int search(int[] nums, int target) {
      // 特殊用例判断
      int len = nums.length;
      if (len == 0) {
          return -1;
      }
      // 在 [left, right] 区间里查找 target
      int left = 0;
      int right = len - 1;
      while (left <= right) {
          // 为了防止 left + right 整形溢出，写成如下形式
          int mid = left + (right - left) / 2;
          if (nums[mid] == target) {
              return mid;
          } else if (nums[mid] > target) {
              // 下一轮搜索区间：[left, mid - 1]
              right = mid - 1;
          } else {
              // 此时：nums[mid] < target，下一轮搜索区间：[mid + 1, right]
              left = mid + 1;
          }
      }
      return -1;
  }
}

Python代码：

class Solution:
  def search(self, nums: List[int], target: int) -> int:
      size = len(nums)
      if size == 0:
          return -1
      left = 0
      right = size - 1
      while left <= right:
          mid = left + (right - left) // 2
          if nums[mid] == target:
              return mid
          elif nums[mid] < target:
              left += 1
          else:
              right -= 1
      return -1

说明：

最简单的二分查找思路：在一个有序数组里查找目标元素。特别像以前电视「猜价格」上的猜价格游戏：运气好，一下子猜中，如果主持人说猜高了，下一步就应该往低了猜，如果主持人说猜低了，下一步就应该就往高了猜。这个思路把待搜索区间 [left, right] 分为 3 个部分：
- mid 位置（只有 1 个元素）；
- [left, mid - 1] 里的所有元素；
- [mid + 1, right] 里的所有元素；
于是，二分查找就是不断地在区间 [left, right] 里根据 left 和 right 的中间位置 mid = (left + right) / 2 的元素大小，也就是看 nums[mid] 与 target 的大小关系：
- 如果 nums[mid] == target ，返回 mid；
- 如果 nums[mid] < target ，由于数组有序，mid 以及 mid 左边的所有元素都小于 target，目标元素可能在区间 [mid + 1, right] 里，因此设置 left = mid + 1；
- 如果 nums[mid] > target ，由于数组有序，mid 以及 mid 右边的所有元素都大于 target，目标元素可能在区间 [left, mid - 1] 里，因此设置 right = mid - 1。
循环体内一定有 3 个分支，并且第 1 个分支一定用于退出循环，或者直接返回目标元素；
退出循环以后，left 和 right 的位置关系为 [right, left] ，返回 left 或者 right 需考虑清楚。

注意事项：

许多刚刚写的朋友，经常在写 left = mid + 1; 还是写 right = mid - 1; 上感到困惑，一个行之有效的思考策略是：永远去想下一轮目标元素应该在哪个区间里；
- 如果目标元素在区间 [left, mid - 1] 里，就需要设置设置 right = mid - 1；
- 如果目标元素在区间 [mid + 1, right] 里，就需要设置设置 left = mid + 1；
考虑不仔细是初学二分法容易出错的地方，这里切忌跳步，需要仔细想清楚每一行代码的含义；
循环可以继续的条件是 while (left <= right)，特别地，当 left == right 即当待搜索区间里只有一个元素的时候，查找也必须进行下去；
int mid = (left + right) / 2; 在 left + right 整形溢出的时候，mid 会变成负数，回避这个问题的办法是写成 int mid = left + (right - left) / 2;。

思路 2：在循环体内部排除元素（在解决复杂问题时非常有用）重点
推荐使用的原因是：需要考虑的细节最少，编码时不容易出错；
根据中间数被分到左边还是右边，一共就以下两种写法。不能死记硬背，应该通过多练习，理解当看到 left = mid 的时候，将取中间数的取法改成上取整的原因。
说明：下面的两版代码不是针对具体的某个问题，而是一种思路。

Java 代码：

public int search(int[] nums, int left, int right, int target) {
    // 在区间 [left, right] 里查找目标元素
    while (left < right) {
        // 选择中间数时下取整
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            // 下一轮搜索区间是 [mid + 1, right]
            left = mid + 1;
        } else {
            // 下一轮搜索区间是 [left, mid]
            right = mid;
        }
    }
    // 退出循环的时候，程序只剩下一个元素没有看到，视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
}

理解模板代码的要点：

核心思想：虽然模板有两个，但是核心思想只有一个，那就是：把待搜索的目标元素放在最后判断，每一次循环排除掉不存在目标元素的区间，目的依然是确定下一轮搜索的区间；
特征：while (left < right)，这里使用严格小于 < 表示的临界条件是：当区间里的元素只有 2 个时，依然可以执行循环体。换句话说，退出循环的时候一定有 left == right 成立，这一点在定位元素下标的时候极其有用；
在循环体中，先考虑 nums[mid] 在满足什么条件下不是目标元素，进而考虑两个区间 [left, mid - 1] 以及 [mid + 1, right] 里元素的性质，目的依然是确定下一轮搜索的区间；
- 注意 1：先考虑什么时候不是解，是一个经验，在绝大多数情况下不易出错，重点还是确定下一轮搜索的区间，由于这一步不容易出错，它的反面（也就是 else 语句的部分），就不用去考虑对应的区间是什么，直接从上一个分支的反面区间得到，进而确定边界如何设置；
根据边界情况，看取中间数的时候是否需要上取整；
- 注意 2：这一步也依然是根据经验，建议先不要记住结论，在使用这个思想解决问题的过程中，去思考可能产生死循环的原因，进而理解什么时候需要在括号里加 1 ，什么时候不需要；
在退出循环以后，根据情况看是否需要对下标为 left 或者 right 的元素进行单独判断，这一步叫「后处理」。在有些问题中，排除掉所有不符合要求的元素以后，剩下的那 1 个元素就一定是目标元素。如果根据问题的场景，目标元素一定在搜索区间里，那么退出循环以后，可以直接返回 left（或者 right）。

两个二分查找法思想的使用建议
简单问题使用思路 1：即要找的那个数的性质特别简单：== 的情况好写，< 的情况好写，> 的情况也好写的时候；
复杂问题使用思路 2：即要找的那个数的性质有点复杂，可能需要借助单调性。用思路 2 就可以把两个边界逐渐向中间收缩，直至找到目标元素；
区别：
- 思路 1 循环体内部有 3 个分支，一定有一个分支用于退出循环或者直接返回，因此无需「后处理」；
- 思路 2 循环体内部有 2 个分支，两个分支都在缩小待搜索区间，退出循环以后，可能需要「后处理」。

例题

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

描述

思路
在循环体内部排除元素即可

循环继续条件，left < right
查找左边界，right = mid
查找右边界时，left = mid，注意此时 mid = left + (right - left) / 2 ，python中整除使用 //
循环结束时，判断nums[left] 是否等于 target。

代码
java代码：

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }
        int firstPosition = findFirstPosition(nums, target);
        if (firstPosition == -1) {
            return new int[]{-1, -1};
        }
        int lastPosition = findLastPosition(nums, target);
        return new int[]{firstPosition, lastPosition};
    }
    private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            // 小于一定不是解
            if (nums[mid] < target) {
                // 下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
    private int findLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) >>> 1;
            // 大于一定不是解
            if (nums[mid] > target) {
                // 下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

python代码：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = 0
        right = len(nums)-1
        if not nums:
            return [-1, -1]
        def get_left_bound(left, right):
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            if nums[left] != target:
                return -1
            return left
        def get_right_bound(left, right):
            while left < right:
                mid = left + (right - left + 1) // 2
                if nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid
            if nums[left] != target:
                return -1
            return left
        left_bound = get_left_bound(left, right)
        right_bound = get_right_bound(left, right)
        return [left_bound, right_bound]

2. 搜索插入位置

描述

思路

考虑特殊情况，我们发现当target大于数组所有元素时，如果我们使用思路2查找模板，循环退出的条件是left == right，很显然不满足条件。所以如果使用思路二需要进行特判：if target > nums[-1]
而查找模板一刚好可以满足退出循环时，left != right，且退出时left 的值刚好等于插入位置。
分析：要找到大于或者等于 target 的第 1 个元素的下标，因此严格小于 target 的元素就不是解。根据这一点写出代码。

代码
Java代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            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;
            }
        }
        return left;
    }
}

Python代码：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left = 0
        right = n -1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

3. 搜索旋转排序数组（搜索一个给定的目标值）

描述

思路

很明显我们要使用二分查找，我们根据nums[mid]和nums[0]值的大小关系以及 nums[mid]和target的大小关系来缩小查找区间。

代码
Java代码：

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

Python代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid+1
                else:
                    right = mid -1
        return -1

4. 搜索旋转排序数组 II （有重复元素）

思路
题目给出的是“旋转排序数组”，是“部分有序数组”，我们同样可以一次排除一半或者一半以上元素的方法，即二分查找法。
二分查找法的本质是排除法，二分只是手段，二分保证了“熵”最大，即在没有任何有效信息的时候，平分是最好的方案。
思路清楚了以后，我们就得确定“有序数组”存在在“原始数组”的哪个子区间里，下面提供了两个比较标准：
1、中间元素和左边界比较；
2、中间元素和右边界比较。
由这两个比较标准就能写出两版不同的代码

代码
Java代码：

class Solution {
    public boolean search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[left] == nums[mid]) {
                left++;
                continue;
            }
            if (nums[left] < nums[mid]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid -1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid -1;
                }
            }
        }
        return false;
    }
}

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        m = len(nums)
        left = 0
        right = m -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True
            if nums[left] == nums[mid]:
                left += 1
                continue
            elif nums[0] < nums[mid]:
                if nums[0] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

5. 寻找旋转排序数组中的最小值

描述

思路

比较nums[mid]和nums[right]的大小，
如果nums[mid] > nums[right]，显然最小元素在[mid + 1, right]之间。
如果nums[mid] < nums[right]，那么将right赋值为mid，因为mid可能为最小的元素。

代码
Java代码：

class Solution {
    public int findMin(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            }
        }
        return nums[left];
    }
}

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
        return nums[right]

6. 寻找旋转排序数组中的最小元素 II

描述

思路
我们依然采用上题的办法，只是当nums[mid] == nums[right]时，我们将right减1，排除一个元素。
代码
Java代码：

class Solution {
    public int findMin(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left];
    }
}

Python代码：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
        return nums[right]

7. 最长上升子序列（二分查找）

描述

思路
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。
同时我们可以注意到 d[i] 是关于 i 单调递增的。因为如果 d[j]≥d[i] 且 j<i，我们考虑从长度为 i 的最长上升子序列的末尾删除i−j 个元素，那么这个序列长度变为 j ，且第 j 个元素 x（末尾元素）必然小于 d[i]，也就小于 d[j]。那么我们就找到了一个长度为 j 的最长上升子序列，并且末尾元素比 d[j] 小，从而产生了矛盾。因此数组 d[] 的单调性得证。

我们依次遍历数组 nums[] 中的每个元素，并更新数组 d[] 和 len 的值。如果 nums[i]>d[len] 则更新 len=len+1，否则在 d[1…len]中找满足 d[i−1]根据 d 数组的单调性，我们可以使用二分查找寻找下标 i，优化时间复杂度。

最后整个算法流程为：
设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums[i] 时：
如果 nums[i]>d[len] ，则直接加入到 d 数组末尾，并更新 len=len+1；
否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k+1]=nums[i]。

以输入序列 [0, 8, 4, 12, 2][0,8,4,12,2] 为例：
第一步插入 0，d = [0]；
第二步插入 8，d = [0, 8]；
第三步插入 4，d = [0, 4]；
第四步插入 12，d = [0, 4, 12]；
第五步插入 2，d = [0, 2, 12]。

最终得到最大递增子序列长度为 3
代码
Javascript代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let d = [];
    for(let num of nums) {
        if (d.length === 0 || num > d[d.length - 1]) {
            d.push(num);
        } else {
            let left = 0;
            let right = d.length - 1;
            let pos = right;
            while (left < right) {
                let mid = parseInt((left + right) / 2);
                if (d[mid] >= num) {
                    pos = mid;
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            d[pos] = num;
        }
    }
    return d.length;
};

def lengthOfLIS(self, nums: List[int]) -> int:
        d = []
        for num in nums:
            if not d or num > d[-1]:
                d.append(num)
            else:
                left = 0
                right = len(d) - 1
                pos = right
                while left < right:
                    mid = left + (right - left) // 2
                    if d[mid] >= num:
                        pos = mid
                        right = mid
                    else:
                        left = mid + 1
                d[pos] = num
        return len(d)

8.平方根

描述

思路
在一个整数范围里查找一个整数，也是二分查找法的应用场景。
分析：根据题目中给出的示例，要我们找的是「边界值」，这个「边界值」的特点如下：

平方以后小于 x 的有可能是解；
平方以后等于 x 的一定是解；
平方以后大于 x 的一定不是解。

根据以上 3 条性质写出代码。这里用「二分查找」的「思路 2」：在循环体内逐渐缩小目标元素的范围，在退出循环以后，剩下的那个元素一定就是目标值。
代码
Python代码：

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        if x == 1:
            return 1
        left = 0
        right = x // 2
        while left < right:
            mid = left + (right - left + 1) // 2
            if mid * mid > x:
                right = mid - 1
            else:
                left = mid
        return left

Java代码：

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        long left = 0;
        long right = x / 2;

        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int)left;
    }
}

9.寻找重复数

描述

思路
方法一：二分法
注意：这个方法使用的前提是，题目中说：

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n）。

个人意见：
通过这个方法知道二分法还可以用于确定一个有范围的整数（这个思路很常见）；
本题的场景和限制是极其特殊的，实际工作中和绝大多数算法问题都不会用「时间换空间」。
这道题要求我们查找的数是一个整数，并且给出了这个整数的范围（在 11 和 nn 之间，包括 1 和 n），并且给出了一些限制，于是可以使用二分查找法定位在一个区间里的整数；

二分法的思路是先猜一个数（有效范围 [left, right]里的中间数 mid），然后统计原始数组中小于等于这个中间数的元素的个数 cnt，如果 cnt 严格大于 mid，（注意我加了着重号的部分「小于等于」、「严格大于」）。根据抽屉原理，重复元素就在区间 [left, mid] 里；

与绝大多数二分法问题的不同点是：正着思考是容易的，即：思考哪边区间存在重复数是容易的，因为有抽屉原理做保证。我们通过一个具体的例子来分析应该如何编写代码；
以 [2, 4, 5, 2, 3, 1, 6, 7] 为例，一共 8 个数，n + 1 = 8，n = 7，根据题目意思，每个数都在 1 和 7 之间。

例如：区间 [1, 7]的中位数是 4，遍历整个数组，统计小于等于 4 的整数的个数，如果不存在重复元素，最多为 4 个。等于 4 的时候区间 [1, 4]内也可能有重复元素。但是，如果整个数组里小于等于 4 的整数的个数严格大于 4 的时候，就可以说明重复的数存在于区间 [1,4]。
代码
Python 二分查找：

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        left = 0
        right = n - 1
        ans = -1
        while left < right:
            mid = (left + right) >> 1
            count = 0
            for i in range(n):
                if nums[i] <= mid:
                    count += 1
            if (count <= mid):
                left = mid + 1
            else:
                right = mid

        return left

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            for (int num : nums){
                if (num <= mid) {
                    count += 1;
                }
            }
            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

Java快慢指针：

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);

        slow = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

龟兔赛跑-Javascript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let slow = 0;
    let fast = 0;
    do{
        slow = nums[slow];
        fast = nums[nums[fast]];
    }while(slow != fast) 
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
};

10.分割数组的最大值

描述

思路
方法一：二分查找，逼近
大于的时候舍弃，小于等于的时候保留，这样左右向中间逼近能找到 M 的最小值，具体可以看题解中唯一的那张图；
理解贪心算法的应用，在从左向右划分组的时候，我们的方案是尽量让一个组有更多的元素，直至超过了设定的临界值（很遗憾，证明已经超出了我的能力范围）。
理解单调性
一个重要的性质：分割数越大，「子数组各自的和的最大值」就越小（非递增，满足单调性），因此可以使用二分查找，定位分割数；
一种「分割方案（分成几个子数组）」对应了一个「子数组各自的和的最大值」；
反过来，一个「子数组各自的和的最大值」对应了一种「分割方案（分成几个子数组）」；
它们是一一对应的关系（关键）。
思路整理（绕了个弯子去逼近）
先找「子数组各自的和的最大值」的中间数（尝试得到的一个值），看看它对应的「分割方案（分成几个子数组）」是多少；
如果「分割方案（分成几个子数组）」比题目要求的 m 还多，说明「子数组各自的和的最大值」还太小，所以下一次搜索应该至少是中位数 + 1（left = mid + 1），它的反面即至多是中位数（right = mid）。

方法二：动态规划
我们可以令 f[i][j] 表示将数组的前 ii 个数分割为 jj 段所能得到的最大连续子数组和的最小值。在进行状态转移时，我们可以考虑第 j 段的具体范围，即我们可以枚举 k，其中前 k 个数被分割为j−1 段，而第 k+1 到第 i 个数为第 j段。此时，这 jj 段子数组中和的最大值，就等于 f[k][j−1] 与 sub(k+1,i) 中的较大值，其中 sub(i,j) 表示数组 nums 中下标落在区间 [i,j] 内的数的和。

由于我们要使得子数组中和的最大值最小，因此可以列出如下的状态转移方程，sub表示数组前缀和：

dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i] - sub[k]))

代码
Java-二分查找：

public class Solution {

    public int splitArray(int[] nums, int m) {
        int max = 0;
        int sum = 0;

        // 计算「子数组各自的和的最大值」的上下界
        for (int num : nums) {
            max = Math.max(max, num);
            sum += num;
        }

        // 使用「二分查找」确定一个恰当的「子数组各自的和的最大值」，
        // 使得它对应的「子数组的分割数」恰好等于 m
        int left = max;
        int right = sum;
        while (left < right) {
            int mid = left + (right - left) / 2;

            int splits = split(nums, mid);
            if (splits > m) {
                // 如果分割数太多，说明「子数组各自的和的最大值」太小，此时需要将「子数组各自的和的最大值」调大
                // 下一轮搜索的区间是 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是上一轮的反面区间 [left, mid]
                right = mid;
            }
        }
        return left;
    }

    /***
     *
     * @param nums 原始数组
     * @param maxIntervalSum 子数组各自的和的最大值
     * @return 满足不超过「子数组各自的和的最大值」的分割数
     */
    private int split(int[] nums, int maxIntervalSum) {
        // 至少是一个分割
        int splits = 1;
        // 当前区间的和
        int curIntervalSum = 0;
        for (int num : nums) {
            // 尝试加上当前遍历的这个数，如果加上去超过了「子数组各自的和的最大值」，就不加这个数，另起炉灶
            if (curIntervalSum + num > maxIntervalSum) {
                curIntervalSum = 0;
                splits++;
            }
            curIntervalSum += num;
        }
        return splits;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{7, 2, 5, 10, 8};
        int m = 2;
        Solution solution = new Solution();
        int res = solution.splitArray(nums, m);
        System.out.println(res);
    }
}

Python动态规划：

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        dp = [[10**18] * (m + 1) for _ in range(n + 1)]
        sub = [0]
        for num in nums:
            sub.append(sub[-1] + num)
        dp[0][0] = 0
        for i in range(1, n + 1):
            # 注意这里j 的遍历范围，为1 到 i 和 m的最小值
            for j in range(1, min(i, m) + 1):
                for k in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i] - sub[k]))
        return dp[n][m]

11.爱吃香蕉的珂珂

描述

思路
二分查找，最少吃一个，最多吃max(piles)个，二分，每次检查mid是否满足H小时内吃完，如果所花时间count > H，显然得多吃，left = mid + 1, 否则 right = mid，逐渐逼近答案。
代码
Python代码：

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        def check(mid):
            count = 0
            for pile in piles:
                if pile % mid == 0:
                    count += pile // mid
                else:
                    count += pile // mid + 1
            return count > H
        max_pile = 0
        for pile in piles:
            max_pile = max(max_pile, pile)

        left = 1
        right = max_pile
        if H == len(piles):
            return max_pile
        while left < right:
            mid = left + (right - left) // 2

            if check(mid):
                left = mid + 1
            else:
                right = mid
        return left

12. 找到K个最接近的元素

描述

思路
分析1：
以 arr = [1, 2, 3, 4, 5, 6, 7] , x = 5, k = 3 为例。
1、一个一个删，因为是有序数组，且返回的是连续升序子数组，所以每一次删除的元素一定是位于边界；
2、一共 7 个元素，要保留 3 个元素，因此要删除 4 个元素；
3、因为要删除的元素都位于边界，于是可以使用双指针对撞的方式确定保留区间，即「最优区间」。
我们再分析一个 x 不在数组中的例子，例如：
数组 arr = [0, 1, 2, 3, 3, 4, 7, 7, 8]，k = 3，x = 5。数组中一共 9 个数，保留 3 个数，则需要删除 6 个数，这里 6 = len(arr) - k。
1、因为 5 - 0 > 8 - 5，所以将 0 删去；
2、因为 5 - 1 > 8 - 5，所以将 1 删去；
3、因为 5 - 2 = 8 - 5，根据题目意思，保留左边的 2 ，所以将 8 删去；
4、因为 5 - 2 > 7 - 5，所以将 2 删去；
5、因为 5 - 3 = 7 - 5，根据题目意思，保留左边的 3 ，所以将 7 删去；
6、因为 5 - 2 = 7 - 5，根据题目意思，保留左边的 3 ，所以将 7 删去；
已经删除了 6 个数，剩下的 [3, 3, 4] 就是最接近 5 的 3 个数。

分析2：
我们知道：如果 x 的值就在长度为 size 的区间内（不一定相等），要得到 size - 1 个符合题意的最接近的元素，此时看左右边界：

左边界与 x 的差值的绝对值较小，删除右边界；
如果右边界与 x 的差值的绝对值较小，删除左边界；
如果左、右边界与 x 的差值的绝对值相等，删除右边界。
讨论「最优区间的左边界」的取值范围：

首先我们讨论左区间的取值范围，使用具体的例子，就很很清楚地找到规律：

1、假设一共有 5 个数，不管 x 的值是多少，在 [0, 1, 2, 3, 4]，找 3 个数，左边界最多到 2；
2、假设一共有 8 个数，不管 x 的值是多少，在 [0, 1, 2, 3, 4, 5, 6, 7]，找 5 个数，左边界最多到 3。

因此，「最优区间的左边界」的下标的搜索区间为 [0, size - k]。注意，这个区间的左右都是闭区间，都能取到。

定位左区间的下标，有一点技巧性，但并不难理解。由排除法的结论，我们从 [0, size - k] 这个区间的任意一个位置（用二分法就是当前候选区间的中位数）开始，定位一个长度为 (k + 1) 的区间，根据这个区间是否包含 x 开展讨论。

1、如果区间包含 x，我们尝试删除 1 个元素，好让区间发生移动，便于定位「最优区间的左边界」的下标；
2、如果区间不包含 x，就更简单了，我们尝试把区间进行移动，以试图包含 x，但也有可能区间移动不了（极端情况下）。

代码
Python 二分查找：

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left = 0
        right = len(arr) - k
        while left < right:
            mid = left + (right - left) // 2
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        return arr[left: left + k]

Java 二分查找：

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - k;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            ans.add(arr[i]);
        }
        return ans;
    }
}

JavaScript 双指针法：

var findClosestElements = function(arr, k, x) {
    while (arr.length > k) {
        if (x-arr[0] > arr[arr.length -1] - x) {
            arr.shift();
        } else {
            arr.pop();
        }
    }
    return arr;
};

13. 转变数组后最接近目标值的数组和

描述

一句话题解：

使用二分法确定一个整数 threshold（就是题目中说的 value），使得这个 threshold 下，「转变后的数组」的和最接近目标值 target；
「转变」的规则是：严格大于 threshold 的元素变成 threshold，那么 threshold 越大，「转变后的数组」的和越大，这是「单调性」

思路
这道题比较麻烦的是求和以后可能不等于 target ，所以让我们求「最接近的方案」。而这个烦人的根源是 value 的取值一定得是整数。正是因为题目说 value 是整数，并且「答案不一定是 arr 中的数字」，因此依然可以使用二分查找法确定这个整数值。

最接近的情况是：选定了一个 value 求和以后，恰恰好等于 target。不过更有可能出现的情况是：value 选得小了，「接近程度」变大，而 value 选得大了，「接近程度」变小，反过来也是有可能的。
查找 - 图14
解决方案是：把边界的上下方的可能的 value 值（一共就两个）都拿出来进行一次比较即可。
代码
如果选择一个阈值 value ，使得它对应的 sum 是第 1 个大于等于 target 的，那么目标值可能在 value 也可能在 value - 1。注意大于等于。
Python 代码：

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        left = 0
        right = 0
        for num in arr:
            right = max(num, right)

        while left < right:
            mid = left + (right - left) // 2
            if self.calc(arr, mid) >= target:
                right = mid
            else:
                left = mid + 1

        sum1 = self.calc(arr, left)
        sum2 = self.calc(arr, left - 1)
        # 注意这里是大于等于
        if sum1 - target >= target - sum2:
            return left - 1
        return left

    def calc(self, arr, mid):
        ans = 0
        for num in arr:
            ans += min(num, mid)
        return ans

如果选择一个阈值 value ，使得它对应的 sum 是最后 1 个小于等于 target 的阈值，那么目标值可能在 value 也可能在 value + 1。
Java代码：

public class Solution {

    public int findBestValue(int[] arr, int target) {
        int left = 0;
        int right = 0;
        // 注意：
        for (int num : arr) {
            right = Math.max(right, num);
        }

        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            int sum = calculateSum(arr, mid);
            // 计算最后 1 个使得转变以后数组的和小于等于 target 的阈值 threshold
            if (sum > target) {
                // 大于等于的就不是解，threshold 太大了，下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索区间是 [mid, right]
                left = mid;
            }
        }

        // 比较阈值线分别定在 left 和 left + 1 的时候与 target 的接近程度
        int sum1 = calculateSum(arr, left);
        int sum2 = calculateSum(arr, left + 1);
        // 注意：这里必须加绝对值，因为有可能出现 sum1 == sum2 < target 的情况
        if (Math.abs(target - sum1) <= Math.abs(sum2 - target)) {
            return left;
        }
        return left + 1;
    }

    private int calculateSum(int[] arr, int threshold) {
        int sum = 0;
        for (int num : arr) {
            sum += Math.min(num, threshold);
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 5};
        int target = 11;
        Solution solution = new Solution();
        int res = solution.findBestValue(arr, target);
        System.out.println(res);
    }
}

查找

前言

思路 1：在循环体内部查找元素（解决简单问题时有用）

思路 2：在循环体内部排除元素（在解决复杂问题时非常有用）重点

两个二分查找法思想的使用建议

例题

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

2. 搜索插入位置

3. 搜索旋转排序数组（搜索一个给定的目标值）

4. 搜索旋转排序数组 II （有重复元素）

5. 寻找旋转排序数组中的最小值

6. 寻找旋转排序数组中的最小元素 II

7. 最长上升子序列（二分查找）

8.平方根

9.寻找重复数

10.分割数组的最大值

11.爱吃香蕉的珂珂

12. 找到K个最接近的元素

13. 转变数组后最接近目标值的数组和