算法学习：二分查找

一、介绍

二分查找的前提

1. 目标函数单调性（单调递增或递减）
2. 存在上下界（bounded）
3. 能够通过索引访问（index accessible）

注：在某些情况下，如果目标函数可以通过一定变换实现单调性，那么也可以使用二分查找。

代码模板

left, right = 0, len(array) - 1 
while left <= right: 
  mid = (left + right) / 2 
  if array[mid] == target: 
    # find the target!! 
    break or return result 
  elif array[mid] < target: 
    left = mid + 1 
  else: 
    right = mid - 1

注：只是一个模板，并非定式。

二、示例

69. x 的平方根

问题描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例

输入：x = 4
输出：2

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

解题思路

二分查找直接开冲！

代码示例（JAVA）

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }

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

---

367. 有效的完全平方数

问题描述

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。

示例

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

解题思路

二分查找进行开方。

代码示例（JAVA）

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 0 || num == 1) {
            return true;
        }

        int left = 1, right = num - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long square = (long) mid * mid;
            if (square == num) {
                return true;
            } 
            if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

---

33. 搜索旋转排序数组

问题描述

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

解题思路

在解这道题之前需要发现：虽然经过旋转，但是这个数组如果一分为二去看，必定有一边具有单调性。
依照这个规律，进行二分查找即可。

代码示例（JAVA）

class Solution {
    public int search(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return -1;
        }
        if (length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int left = 0, right = length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 左半边有序
            if (nums[left] <= nums[mid]) {
                // 且落在左半边
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    // 落在右半边
                    left = mid + 1;
                }
            } else {
                // 右半边有序
                // 落在右半边
                if (nums[mid] < target && target <= nums[length - 1]) {
                    left = mid + 1;
                } else {
                    // 落在左半边
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

---

74. 搜索二维矩阵

问题描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例

解题思路

根据这个矩阵的特性可知，这个矩阵可以视为一个单调递增的数组；因此，这道题继续使用二分查找。

代码示例（JAVA）

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int rowLenth = matrix[0].length;
        int left = 0, right = row * rowLenth - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midY = mid % rowLenth;
            int midX = (mid - midY) / rowLenth;
            if (matrix[midX][midY] == target) {
                return true;
            }
            if (matrix[midX][midY] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

---

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

问题描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例

解题思路

旋转排序数组一分为二，必定有一边是有序的；
此时，取有序区间的左边界与当前min做比较并取最小，然后舍弃这个区间；
继续进行二分查找找有序边界重复以上操作直至结束。

代码示例（JAVA）

class Solution {
    public int findMin(int[] nums) {
        int length = nums.length;
        int left = 0, right = length - 1;
        int ans = nums[0];

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 左边有序
            if (nums[left] <= nums[mid]) {
                // 直接拿左边界的左（left）进行比较
                if (nums[left] < ans) {
                    ans = nums[left];
                }
                left = mid + 1;
            } else {
                // 右边有序，直接拿右边界的左（mid）进行比较
                if (nums[mid] < ans) {
                    ans = nums[mid];
                }
                right = mid - 1;
            }
        }
        return ans;
    }
}