文章目录
  1. 1. 二分查找解决问题所需要的条件
  2. 2. 二分查找典型问题
  3. 3. 二分问题标准代码模版
  4. 4. 求解二分查找问题
    1. 4.1. Sqrt(x)
      1. 4.1.1. 审题,沟通
      2. 4.1.2. 可能解及对应复杂度分析
      3. 4.1.3. 实现
      4. 4.1.4. 测试用例
      5. 4.1.5. 衍生问题

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

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

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

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

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

二分查找典型问题

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

二分问题标准代码模版

循环方式的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
}

递归方式实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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值(也就是平方操作后最后一个不大于目标值的整数), 所以返回值有可能可能不会与目标值严格相等,所以需要稍微对标准的二分查找的代码做技术处理。
具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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$

1
2
3
4
5
6
7
8
9
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 参考实现 以及对应测试工程

文章目录
  1. 1. 二分查找解决问题所需要的条件
  2. 2. 二分查找典型问题
  3. 3. 二分问题标准代码模版
  4. 4. 求解二分查找问题
    1. 4.1. Sqrt(x)
      1. 4.1.1. 审题,沟通
      2. 4.1.2. 可能解及对应复杂度分析
      3. 4.1.3. 实现
      4. 4.1.4. 测试用例
      5. 4.1.5. 衍生问题