二分法 - 简书

有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。

解法：二分法
1）第k小的数字意味着小于等于它的元素一共有k个，大于它的数字有n^2 - k个。假设某个数为mid：如果小于等于mid的元素个数小于k，说明mid不是第k小的数，比mid小的数就更不可能是了，所以第k小的数至少是mid + 1；如果小于等于mid的元素个数大于等于k，说明mid可能为第k小的数，比它小的数也有可能是答案。
2）这就是二分法的思路。假定查找的范围为[left, right]，首先计算int mid = left + (right - left) / 2；然后在矩阵中计数有多少个元素小于等于mid，这个数量为count。
如果count < k，那么第k小的数至少为mid + 1，所以left = mid + 1。反之，right = mid。
循环结束的条件为left >= right，此时left即为答案。
如果在有序矩阵中计数有多少个元素小于等于mid：参看下列图示的思路。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {

        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (getCountNotMoreThan(matrix, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public int getCountNotMoreThan(int[][] matrix, int mid) {
        int count = 0;
        int n = matrix.length;
        int x = 0;
        int y = n - 1;
        while (x < n && y >= 0) {
            if (y >= 0 && matrix[x][y] <= mid) {
                count += y + 1;
                x++;
            } else {
                y--;
            }
        }
        return count;
    }
}

实现 pow(x, n)

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

二分法+递归
1）当我们要计算 $x^n$ 时，我们可以先递归地计算出 $y = x^{\lfloor n/2 \rfloor}$ ，其中 $\lfloor a \rfloor$ 表示对 a 进行下取整；
2）根据递归计算的结果，如果 n 为偶数，那么 $x^n = y^2$ 如果 n 为奇数，那么 $x^n = y^2 * x$ ;
3）递归的边界为 n = 0，任意数的 0 次方均为 1。

由于每次递归都会使得指数减少一半，因此递归的层数为 O(logn)，算法可以在很快的时间内得到结果。

public static double myPow(double x, int n) {

        if(n >= 0){
            return myPow2(x, n);
        }else {
            return 1.0 / myPow2(x, Math.abs(n));
        }
    }

    public static double myPow2(double x, long n){
        if(n == 0){
            return 1;
        }
        long half = n / 2;
        double res = myPow2(x, half);
        return res * res * (n % 2 == 0 ? 1 : x);
    }

寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -无穷。

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5，其峰值元素为 6。

说明:你的解法应该是 O(logN) 时间复杂度的。

二分法
首先从数组 nums 中找到中间的元素 mid。若该元素恰好位于降序序列或者一个局部下降坡度中（通过将 nums[i] 与右侧比较判断)，则说明峰值会在本元素的左边。于是，我们将搜索空间缩小为 mid 的左边(包括其本身)，并在左侧子数组上重复上述过程。

若该元素恰好位于升序序列或者一个局部上升坡度中（通过将 nums[i]与右侧比较判断)，则说明峰值会在本元素的右边。于是，我们将搜索空间缩小为 mid 的右边，并在右侧子数组上重复上述过程。

就这样，我们不断地缩小搜索空间，直到搜索空间中只有一个元素，该元素即为峰值元素。

public int findPeakElement(int[] nums) {
        return bisection(nums, 0, nums.length - 1);
    }

    public int bisection(int[] nums, int L, int R) {
        if (L == R) {
            return L;
        }
        int mid = (L + R) / 2;
        if (nums[mid] > nums[mid + 1]) {
            return bisection(nums, L, mid);
        }
        return bisection(nums, mid + 1, R);
    }

寻找旋转排序数组中的最小值(https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0

二分法
1）如果末尾元素小于首元素，说明进行了旋转；根据如下特点进行二分法：

找到变化点即找到最小元素，所以我们的任务就是找到变化点；
下面是关于变化点的特点：
所有变化点左侧元素 > 数组第一个元素
所有变化点右侧元素 < 数组第一个元素
所以反推，如果
中间点元素 > 数组第一个元素，那么变化点在中间点元素右侧；
中间点元素 < 数组第一个元素，那么变化点在中间点元素左侧；
2）如果末尾元素大于首元素，说明没有旋转，返回第一个元素即可

 public static int findMin(int[] nums) {
        if(nums[nums.length - 1] < nums[0]){
            return findMin(nums, 0, nums.length - 1); // 翻转了
        }else {
            return nums[0];
        }
    }

    public static int findMin(int[] nums, int L, int R) {

        if (L == R) {
            return nums[L];
        }

        int mid = L + (R - L) / 2;
        if (nums[mid] < nums[0]) {
            return findMin(nums, L, mid);
        } else if(nums[mid] == nums[0]){
            return Math.min(nums[L], nums[R]);
        } else {
            return findMin(nums, mid + 1, R);
        }
    }

寻找重复数(https://leetcode-cn.com/problems/find-the-duplicate-number/)

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

此题的难点在于只能使用O(1)的空间。
二分法
注意：二分法的二分对象不一定是题目中给定的数组，因为没有排序的数组是无法进行二分；有时候知道某个数的范围为（0， n），而题目是求这个数，那么可以对这个数的范围进行二分。所以关键是知道怎么二分。

我们定义 cnt[i] 表示nums[] 数组中小于等于 i 的数有多少个，假设我们重复的数是 target，那么[1,target−1]里的所有数满足cnt[i]≤i，[target,n] 里的所有数满足 cnt[i]>i，具有单调性。利用此性质可以进行二分（二分可以用迭代或者递归，这里使用迭代）。

 public static int findDuplicate(int[] nums) {

        int n = nums.length;
        int max = n - 1;
        int min = 1;

        int L = min;
        int R = max;

        while (L < R) {
            int mid = L + (R - L) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= mid) {
                    count++;
                }
            }
            if (count <= mid) {
                L = mid + 1;
            } else {
                R = mid;
            }
        }

        return L;
    }

快慢指针（Floyd 判圈算法）
我们对nums[] 数组建图，每个位置 i连一条i→nums[i] 的边。位置i相当于Node的val，nums[i]相当于Node的next指针。因为nums[i]的取值为（1，n），所以可行。由于存在的重复的数字 target，因此target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的 target 就是这个环的入口。使用快慢指针寻找环的入口位置。
注意：节点的.next操作，正好是这里的nums[]操作；所以快指针的.next.next操作，对应这里的nums[nums[]]操作。

 public static int findDuplicate2(int[] nums) {

        // 快慢指针找到相遇点
        int slow = 0;
        int fast = 0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 同时遍历找到环的入口, 即重复元素
        int ptr1 = 0;
        int ptr2 = fast;
        while (ptr1 != ptr2){
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }

        return ptr1;
    }

搜索旋转排序数组(https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

二分法
数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分搜索吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分搜索的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分搜索的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足(nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

public static int search2(int[] nums, int target){
        if(nums.length == 0){
            return -1;
        }

        if(nums[0] <= nums[nums.length-1]){ // 未翻转
            return findTarget(nums, 0, nums.length-1, target);
        }else { // 翻转
            return biSearch(nums, 0, nums.length-1, target);
        }
    }

    public static int biSearch(int[] nums, int L, int R, int target){

        if(L > R){
            return -1;
        }

        if(L == R){
            return nums[L] == target ? L : -1;
        }

        int med = L + (R - L)/2;

        if(nums[L] <= nums[med]){ // 左半部分有序
            if(target >= nums[L] && target <= nums[med]){
                return findTarget(nums, L, med, target); // target位于有序部分
            }else { // target位于无序部分
                return biSearch(nums, med+1, R, target);
            }
        }else { // 右半部分有序
            if(target >= nums[med+1] && target <= nums[R]){ // target位于有序部分
                return findTarget(nums, med+1, R, target);
            }else { // target位于无序部分
                return biSearch(nums, L, med, target);
            }
        }
    }

public static int findTarget(int[] nums, int L, int R, int target) {

        if(L > R){
            return -1;
        }

        if (L == R) {
            return nums[L] == target ? L : -1;
        }

        int med = L + (R - L) / 2;
        if (target < nums[med]) {
            return findTarget(nums, L, med - 1, target);
        } else if (target == nums[med]) {
            return med;
        } else {
            return findTarget(nums, med + 1, R, target);
        }
    }

另外一种，可以先用二分法找出翻转点，然后判断target在哪一段有序的数组中，然后寻找即可。

public static int search(int[] nums, int target) {

        if(nums.length == 0){
            return -1;
        }

        if(nums[0] <= nums[nums.length-1]){ // 未翻转
            return findTarget(nums, 0, nums.length-1, target);
        }else { // 翻转
            int minInd = findReversePointInd(nums, 0, nums.length - 1);// 找出最小元素下标
            if (target > nums[0]) {
                return findTarget(nums, 1, minInd - 1, target);
            } else if(target == nums[0]){
                return 0;
            } else {
                return findTarget(nums, minInd, nums.length - 1, target);
            }
        }
    }

    public static int findReversePointInd(int[] nums, int start, int end) {

        if (start == end || start == end - 1) {
            return nums[start] < nums[end] ? start : end;
        }

        int med = start + (end - start) / 2;
        if (nums[med] < nums[start]) {
            return findReversePointInd(nums, start, med);
        } else {
            return findReversePointInd(nums, med, end);
        }
    }

    public static int findTarget(int[] nums, int L, int R, int target) {

        if(L > R){
            return -1;
        }

        if (L == R) {
            return nums[L] == target ? L : -1;
        }

        int med = L + (R - L) / 2;
        if (target < nums[med]) {
            return findTarget(nums, L, med - 1, target);
        } else if (target == nums[med]) {
            return med;
        } else {
            return findTarget(nums, med + 1, R, target);
        }
    }

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

二分法
1）使用二分法分别找到左边界和右边界；
2）注意med的取值范围，避免无线循环；
3）注意L和R的大小关系，确保循环正确结束；

public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        if(n == 0){
            return new int[]{-1,-1};
        }
        int left = searchLeftBoarder(nums, 0, n - 1, target);
        int right = searchRightBoarder(nums, 0, n - 1, target);
        return new int[]{left, right};
    }

    public int searchLeftBoarder(int[] nums, int L, int R, int target) {
        if (L >= R) {
            if (nums[R] == target) {
                return R;
            } else {
                return -1;
            }
        }
        int med = (L + R) / 2; // L <= med < R
        if (nums[med] >= target) {
            return searchLeftBoarder(nums, L, med, target);
        } else {
            return searchLeftBoarder(nums, med + 1, R, target);
        }
    }

    public int searchRightBoarder(int[] nums, int L, int R, int target) {
        if (L >= R) {
            if (nums[L] == target) {
                return L;
            } else {
                return -1;
            }
        }
        int med = (L + R) / 2; // L <= med < R
        if (nums[med] < target) {
            return searchRightBoarder(nums, med + 1, R, target);
        } else if (nums[med] == target) {
            if (nums[med + 1] == target) {
                return searchRightBoarder(nums, med + 1, R, target);
            } else {
                return med;
            }
        } else {
            return searchRightBoarder(nums, L, med - 1, target);
        }
    }

搜索二维矩阵

二分法
1）先对最后一列进行二分法找到对应行
2）再对该行进行二分法查找
递归实现二分法

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0){
            return false;
        }
        int n = matrix[0].length;
        if(n == 0){
            return false;
        }
        // 二分法确定行数
        int row = biSearch(matrix, n-1, target, 0, m-1);
        if(row == -1){
            return false;
        }
        // 二分法确定是否在此行中
        return biSearch(matrix[row], target, 0, n-1);
    }

    public int biSearch(int[][] matrix, int col, int target, int min, int max){
        if(min == max){
            if(matrix[min][col] >= target){
                return min;
            }else {
                return -1;
            }
        }
        int med = (min + max) / 2; // min <= med < max
        if(matrix[med][col] < target){
            return biSearch(matrix, col, target, med + 1, max);
        }else if(matrix[med][col] == target){
            return med;
        }else {
            return biSearch(matrix, col, target, min, med);
        }
    }

    public boolean biSearch(int[] nums, int target, int min, int max){
        if(min >= max){
            return nums[min] == target;
        }
        int med = (min + max) / 2; // min <= med < max
        if(nums[med] < target){
            return biSearch(nums, target, med + 1, max);
        }else if(nums[med] == target){
            return true;
        }else {
            return biSearch(nums, target, min, med - 1);
        }
    }

迭代实现二分法

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0){
            return false;
        }
        int n = matrix[0].length;
        if(n == 0){
            return false;
        }
        // 二分法确定行数
        int row = getRow(matrix, target);
        if(row == -1){
            return false;
        }
        // 二分法确定是否在此行中
        return hasTarget(matrix, row, target);
    }

    public int getRow(int[][] matrix, int target){
        int m = matrix.length;
        int n = matrix[0].length;
        int top = 0;
        int bot = m-1;
        while (top < bot){
            int med = (top + bot) / 2; // med >= top && med < bot
            if(matrix[med][n-1] < target){
                top = med + 1;
            }else {
                bot = med;
            }
        }
        if(matrix[top][n-1] >= target){
            return top;
        }else {
            return -1;
        }
    }

    public boolean hasTarget(int[][] matrix, int rowInd, int target){
        int n = matrix[0].length;
        int left = 0;
        int right = n - 1;
        while (left < right){
            int med = (left + right) / 2; // med >= left && med < right
            if(matrix[rowInd][med] < target){
                left = med + 1;
            }else if(matrix[rowInd][med] > target){
                right = med - 1;
            }else {
                return true;
            }
        }
        return matrix[rowInd][left] == target;
    }