二分查找问题及对应解决思路

文章目录

1. 二分查找解决问题所需要的条件
2. 二分查找典型问题
3. 二分问题标准代码模版
4. 求解二分查找问题
1. 4.1. Sqrt(x)

二分查找问题是算法问题中比较经典的问题之一，以其$O(log)$时间复杂度的算法效率独领风骚。

二分查找解决问题所需要的条件

既然二分查找在时间复杂度上这么优秀，为什么不在所有的查找问题中使用这个“银弹”呢？我们都知道在软件工程中不存在所谓的银弹，“元数据结构”目前也只是存在于理论家和计算机哲学家的思维之中。
话说回来，那么使用二分查找解决问题到底需要什么样的条件呢？

对应的数据结构必须是支持使用数组下标进行$O(1)$随机访问元素的数组
数组的元素必须有序

其实这样的两个条件要求已经很高了，
首先数组在内存的分配要求的是连续的内存空间；
其次还要求数组是一个有序的，如果不是有序的就需要先排序再使用；

二分查找典型问题

Pow(x, n)
Sqrt(x)
Divide Two Integers

二分问题标准代码模版

循环方式的实现：

public int binarySearch(int[] nums, int target) {
  int left = 0;
  int right = nums.length;
  while (left <= right) {
    int mid = left + （(right - left) >> 1);
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else {
        right = mid - 1;
    }
  }

  return -1
}

递归方式实现：

public int binarySearch(int[] nums, int target) {
  if (nums == null || nums.length == 0) return -1;
  return _binarySearchReccursion(nums, 0, nums.length - 1, target);
}
private int _binarySearchReccursion(int[] nums, int left, int right, int target) {
  if (left > right) return -1;

  int mid = left + ((right - left) >> 1);
  if (nums[mid] == target) {
    return mid;
  } else if (nums[mid] > target) {
    return _binarySearchReccursion(nums, left, right - 1);
  } else {
    return _binarySearchReccursion(nums, left + 1, right);
  }
}

求解二分查找问题

Sqrt(x)

审题，沟通

首先是对于题目中不明确的地方进行沟通和澄清，本题是求解一个整数的平方根，那么输入的参数是Int的整个取值范围($[- 2^{31} , 2^{31}-1]$)么?还是只是正整数部分? 如果输入参数是负整数是直接返回特定的负数（比如 -1）还是抛出异常（例如：runtimeException）？

可能解及对应复杂度分析

其次，对于本题会有以下的这些可能解法：

调用系统内建函数
时间复杂度为$O(log^n)$
使用二分查找在区间$[0, x]$内进行二分查找
为什么可以用二分查找来解决？因为 $x^{\frac{1}{2}}$函数在$[0, +\infty)$区间内单调递增，符合数组和有序的条件。

时间复杂度：$O(log^n)$
使用牛顿迭代法进行
使用纯数学（数值分析）方式迭代逼近求解近似值

时间复杂度: $O(log^n)$

首先第一个在实际工程中应该是第一选择，库函数在实际的项目中有过多种优化，所以使用库函数往往是工程中的第一选择。
说回问题本身，作为一个考察算法基本功的题目，实现第二个算法还是有必要的：

实现

由于LeetCode 原题返回值是int值（也就是平方操作后最后一个不大于目标值的整数），所以返回值有可能可能不会与目标值严格相等，所以需要稍微对标准的二分查找的代码做技术处理。
具体代码如下：

int mySqrt(int x) {
  if (x < 0) return -1;
  if (x == 0 || x == 1) return x;
  int left = 0;
  int right = x;
  int result = 0;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (mid == x / mid) return mid;
    else if (mid > x / mid) right = mid - 1;
    else {
      left = mid + 1;
      result = mid;
    }
  }

  return result;
}

牛顿迭代公式：
$x_{n + 1} = x_n - \frac{f(x_n)}{f^\prime (x_n)}$
继续推导有：
$x_{n + 1} = (x_{n} + \frac{y_0}{x_n}) / 2$

int mySqrt(int x) {
  if (x < 0) return -1;
  if (x == 0 || x == 1) return x;
  int result = x;
  while (result > x / result) {
    result = (result + x / result) / 2;
  }
  return result;
}

测试用例

HappyCase：

x == 4
x == 10

BadCase:

测试部分特别需要注意的是几个边界用例的情况：

x == 0
x == Integer.MAX_VALUE

详细的测试工程代码已在我的Github工程中实现，参见Github : mySqrt mySqrtRound mySqrtZero mySqrtBigInt

衍生问题

既然是求解平方根的数值计算问题，是否可以返回一个带有一定精度（$10^-5$）的浮点值呢？
方法定义如下：

1
2
3

float mSqrt(int x, double epsilon) {

}

请思考，动手写过代码后再查看Github 参考实现以及对应测试工程