二分查找的思考

left左边的一定比target小，left对应的元素为第1个不小于target的。
因此，如果nums中target不存在，left就是target要插入的位置。
经典的二分查找的算法：

    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int 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) {
                right = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

进一步的题目：

算法题目.png

题解：

public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }

        int left = 0;
        int 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 {
                right = mid - 1;
            }
        }

        if(left < 0|| left >= nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        } else {
            int[] pos = new int[2];
            pos[0] = left;
            while(left < nums.length && nums[left] == target) {
                pos[1] = left;
                left++;
            }
            return pos;
        }
    }

进一步引申，看leetcode题目：
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1：

输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：

输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：

输入：nums = [1,4,4], m = 3
输出：4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-array-largest-sum

相似的思想：
left -----------------------------------> right
从左至右，越往后需要的分割数越小。
left左边元素的分割数一定大于m个，left为第1个分割数不超过m的。
如果发现了分割数等于m的，就会继续往左边赶，直到right < left。
题解：

public int splitArray(int[] nums, int m) {
        int left = 0;
        int right = 0;
        for(int num : nums) {
            left = Math.max(num, left);
            right += num;
        }
        
        int mid = 0;
        while(left <= right) {
            mid = left + (right - left) / 2;
            int splits = splits(nums, mid);
            if(splits > m) {
                left = mid + 1;
            } else if(splits < m) {
                right = mid - 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 当各自和的最大值不超过maxIntervalSum时，至少需要的分割数。
     * 注意：分割数不能太少，太少的话各自和的最大值肯定会超过maxIntervalSum。
     * @param nums
     * @param maxIntervalSum
     * @return
     */
    private int splits(int[] nums, int maxIntervalSum) {
        int splits = 1;
        int cnt = 0;
        for(int num : nums) {
            if(cnt + num > maxIntervalSum) {
                splits++;
                cnt = 0;
            }
            
            cnt += num;
        }
        return splits;
    }

再看另外一道题目：

719. Find K-th Smallest Pair Distance.png

题目要寻找数组中任意两对之间第k小的距离，先把数组按升序排好，那么最小距离一定是0（两个数相等），最大距离一定是nums[nums.length - 1] - nums[0]。即：

    int left = 0;
    int right =  nums[nums.length - 1] - nums[0];
    int mid = left + (right - left) / 2

对于任一left和right之间的值mid，假设数组中任意两对距离不大于mid的个数为count。若count < k，则mid偏小了，需要调大；若count > k，则mid偏大了，需要调小；若count == k，则mid可能是第k小的距离，但是mid不一就是数对的距离值，需要寻找左边界，因此仍需要继续往小调，直到找到左边界。

     public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums[nums.length - 1] - nums[0];

        while(left <= right) {
            int mid = left + (right - left) / 2;
            int start = 0;
            int count = 0;

            for(int i = 0 ; i < nums.length; i++) {
                while(nums[i] - nums[start] > mid) {
                    start++;
                }

                count += i - start;
            }

            if(count < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

再看另外一道题目：
思路：
确定左右边界的范围：
左边界：要取k个数字在数组中，那么左边界范围的最左边可以取到：0，左边界范围的最右边可以取到：数组长度 - k；
找到满足条件的左边界：如果最靠近x的不止k个数，需要继续向右边界靠近，直至找到左边界。

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

 public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - k;

        int mid;
        while(left < right) {
            mid = left + (right - left) / 2;
            if(mid + k < arr.length && (x - arr[mid]) > (arr[mid + k] - x)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        List<Integer> result = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            result.add(arr[left + i]);
        }
        return result;
    }