面试题:二分法代码实现求一个数的平方根
2020-01-17 本文已影响0人
秋天的铁工匠
先思考一个开发场景下的问题。
- 假设有 1000 条订单数据，已经按照订单金额从小到大排序，每个订单金额都不同，并且最小单位是元。我们现在想知道是否存在金额等于 19 元的订单。如果存在，则返回订单数据，如果不存在则返回 null。
这里有个游戏的例子
- 二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如说，我们现在来做一个猜字游戏。我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么。猜的过程中，你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。你来想想，如何快速猜中我写的数字呢？
- 假设我写的数字是 23，你可以按照下面的步骤来试一试。（如果猜测范围的数字有偶数个，中间数有两个，就选择较小的那个。）
image.png
为了方便理解，我们假设只有 10 个订单，订单金额分别是：8，11，19，23，27，33，45，55，67，98。
还是利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围。为了更加直观，我画了一张查找过程的图。其中，low 和 high 表示待查找区间的下标，mid 表示待查找区间的中间元素下标。
image.png
总结: 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
上面的例子来自王争老师
关于二分法的几个问题
- 在学习之前先了解下面两段代码
- 第一段代码：二分查找算法实现
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low+((high-low) >>1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
这段代码有三个地方需要注意
- 循环结束条件：必须是
low <= high 而不是 low<high
- mid 的取值
int mid = low+((high-low) >>1)不能错写成 int mid = low+(high-low) >>1; 因为 运算符的优先级问题。
- low 和 high 的更新
low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。
- 第二段代码：递归实现。
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
return bsearchInternally(a, 0, n - 1, val);
}
private int bsearchInternally(int[] a, int low, int high, int value) {
if (low > high) return -1;
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
return bsearchInternally(a, mid+1, high, value);
} else {
return bsearchInternally(a, low, mid-1, value);
}
}
如何使用二分法和牛顿迭代法实现”求一个数的平方根的实现"
- 面试中往往不会让我们使用任何的关于 Math类的方法去实现这个需求。
- 二分法实现代码:
package com.dc.canal.example;
import java.math.BigDecimal;
/**
* @ClassName SqrtUtil
* @Description TODO
* @Author fangxianyang
* @Date 2020/1/1711:05 上午
**/
public class SqrtUtil {
/**
* 方法1 精确度差
* @param data
* @return
*/
public static double getSquareRoot(int data){
if(data < 0){
return -1;
}
double low = 0.0;
double high = data;
double mid = 0.0;
while(isNumOfDigLessThenInput(mid, 6) ){
mid = low + ((high - low) / 2);
if(data == mid*mid){
return mid;
}else if(data < mid*mid){
high = mid;
}else{
low = mid;
}
}
return mid;
}
private static boolean isNumOfDigLessThenInput(double data,int num){
String dataStr = String.valueOf(data);
int index = dataStr.indexOf(".");
if(index == -1){
return true;
}
int numofDig = dataStr.length() - index;
return numofDig <= 6;
}
/**
* 方法2，易于理解，精确度高
* @param a
* @return
*/
public static Double squareRoot(int a){
double x = 0;
double low = 0;
double high = a;
while(low<=high){
x = (low+high)/2;
if(x>a/x){
high = x-0.000001;
}
//防止溢出
if(x<a/x){
low = x+0.000001;
}
if(x==a/x){
//刚好整除
return x+0.000001;
}
}
//精确到六位小数
return new BigDecimal(x).setScale(6, BigDecimal.ROUND_HALF_UP).doubleValue();
}
public static void main(String[] args) {
System.out.println( SqrtUtil.squareRoot(5));
}
}
代码结果：
image
- 牛顿迭代法实现原理和代码可看leetcode 高赞回答 回答地址
二分法的时间复杂度是多少
- 我们假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。
image
- 可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。
为什么二分法使用数组作为数据结构，链表可以吗？
-
二分查找 数组查询时间复杂度 O(logn)。
-
假设链表长度为n，二分查找每次都要找到中间点(计算中忽略奇偶数差异):
第一次查找中间点，需要移动指针n/2次；
第二次，需要移动指针n/4次；
第三次需要移动指针n/8次；
......
以此类推，一直到1次为值 -
总共指针移动次数(查找次数) = n/2 + n/4 + n/8 + ...+ 1，这显然是个等比数列，根据等比数列求和公式：Sum = n - 1.
-
最后算法时间复杂度是：O(n-1)，忽略常数，记为O(n)，时间复杂度和顺序查找时间复杂度相同
-
但是稍微思考下，在二分查找的时候，由于要进行多余的运算，严格来说，会比顺序查找时间慢
如何快速定位IP对应的省份地址？
- 此问题可以使用二分法的变形方式实现
- 二分法一共四种变形方式
第一种：查找第一个值等于给定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
第二种:查找最后一个值等于给定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
第三种:查找第一个大于等于给定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
第四种:查找最后一个小于等于给定值的元素
public int bsearch7(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
对于我们的问题可以使用第四种变形实现 快速定位IP对应的省份地址问题
- 实现思路：
- 如果 IP 区间与归属地的对应关系不经常更新，我们可以先预处理这 12 万条数据，让其按照起始 IP 从小到大排序。如何来排序呢？我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。
- 然后，这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。
- 当我们要查询某个 IP 归属地时，我们可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找。
如果有序数组是一个循环有序数组，比如 4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？
- 此题为leetcode低33题。
- 实现代码：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
int mid = left + (right-left)/2;
while(left <= right){
if(nums[mid] == target){
return mid;
}
if(nums[left] <= nums[mid]){ //左边升序
if(target >= nums[left] && target <= nums[mid]){//在左边范围内
right = mid-1;
}else{//只能从右边找
left = mid+1;
}
}else{ //右边升序
if(target >= nums[mid] && target <= nums[right]){//在右边范围内
left = mid +1;
}else{//只能从左边找
right = mid-1;
}
}
mid = left + (right-left)/2;
}
return -1; //没找到
}
}
欢迎关注“会讲历史的程序员”公众号，一起学习。
-
来张本人头像o(￣▽￣)ｄ，快来关注。
image
