惊了！二分居然有这么多变化！？

「爱情、让人受尽委屈。」 2022-09-08 00:29 114阅读 0赞

上篇说到超超早经历面试官关于Map的拷问过程中，面试官没有继续深究Map的并发，而是抛出了一道根据废纸篓改编的算法题，来看超超如何解答吧。

整数域二分

面试官：你看废纸篓中（回收站）的文件是可以按名称排序的，假设文件的名称都可以用ASCII码转化成一个具体的数字，比如“plan.txt”将每位字母转化成数字后相加最终结果为825，现在要求你设计一个find方法可以用文件名快速查到文件对应的位置该怎么做？

考点：**二分性质**

超超：（这是想考我查找算法吗，最简单的方法应该是线性查找，用一个for循环遍历废纸篓中所有文件便可得出答案，但这是面试题呀，不能这样的！有了！）这里废纸篓中的一系列文件可以看成一个数组，可以利用废纸篓的名称排序功能对数组排序。对于排序好的数组就满足二分法的**有序性**和**查找特定元素**俩个必要条件了。

假设文件抽象出来的数组为nums = \[-1,0,3,5,9,12\]，需要查的目标文件为target = 9。（：确定好可以用二分法之后就可以按照我在「Golang面试宝典」上学到的步骤进行了????。

**第一步**：写出二分法模板

func search(nums []int, target int) int {
      //初始化游标
      left := ...
      right := ...
      for 满足循环的条件{
        //直接写(right+left)极端情况可能会导致和溢出
        mid := left + (right-left)>>1
        if nums[mid] > target {  
          right = ... //target在mid的右半边
        } else if nums[mid] < target {
          left = ...  //target在mid的左半边
        } else if nums[mid] == target {
          return mid  //找到目标元素
        }
      }
      return -1
    }

**第二步**：画出mid变化的示意图，确定mid移动过程中left和right变化

![1be7db7ac5cceee03fd9b9d8799c460e.png][]

nums\[mid\] = 3小于target9，因此target在mid的右半部区域，使left = mid+1，在mid右半边区域查找。

![7bb678623557068f4599b0270dd215fe.png][]

nums\[mid\] = 9等于target，俩次就找到了这个数，时间复杂度为O(logn)。

**第三步**：根据示意图完善模板代码

func search(nums []int, target int) int {
      left := 0
      right := len(nums) - 1  //注意
      for left <= right {  //注意
        mid := left + (right-left)>>1
        if nums[mid] > target {  
          right = mid - 1  //注意
        } else if nums[mid] < target {
          left = mid + 1
        } else if nums[mid] == target {
          return mid
        }
      }
      //数组中无目标值
      return -1
    }

按步骤写，就能避开二分法的众多坑点了，哈哈！

面试官：不错，二分法虽简单，但是能快速写对的人还真不多。我看你写的for判断条件是left <= right，如果改成left < right，那么代码改怎么写呢？

考点：**二分法的俩种写法**

超超：区别在于是否包含最右边的边界值，因为将left <= right改为left < right后，那么当left == right时，不会再进入循环体，所以为了保证left = right时nums\[left\]是被遍历过了的，right初始化时就取值为len(nums)。

这样在for循环中就能保证是在这样一个左闭右开的区间\[left,right)，那么right在循环体中的赋值应该为right = mid而非right = mid-1，因为右半边是开区间，取mid-1就无法验证到nums\[mid-1\]是否是目标值。（：这是想把我往坑点里面带吗？

代码如下：

func search(nums []int, target int) int {
      left := 0
      right := len(nums)  //注意
      for left < right {  //注意
        mid := (left + right) >> 1
        if nums[mid] < target {
          left = mid + 1
        } else if nums[mid] == target {
          return mid
        } else {
          right = mid  //注意
        }
      }
      //数组中无目标值
      return -1
    }

#####     #####

带精度的二分

面试官：那再看这样一个问题。实现 float64 sqrt(float64 x) 函数，计算并返回 *x* 的平方根，其中 *x* 是非负浮点数，返回精度为0.01的开方值。

##### 示例 1: #####

输入: 2
    输出: 1.41

**示例 2:**

输入: 8
    输出: 2.82

考点：**精度****二分法**

超超：这题应该还是二分相关的问题，因为任意一个数的开方结果都是大于0的，指向最左边的游标left可以从0开始，指向最右边的游标right可以从被开方数x开始。这样就变成了从有序数组\[0.00,0.01,0.02.......x.00\]中查找开方数了。确定满足二分法的**有序性**和**查找特定元素**俩个必要条件后，接着按步骤解题即可。

**第一步**：写出二分法模板

‍

**第二步**：以根号二为例画出mid变化的示意图，确定mid移动过程中left和right变化(节约空间这里省去用不上的节点)

![4a8d759420d91bc51011291a6259a0c6.png][]

nums\[mid\] \* nums\[mid\] < 2因此使**left = mid**，这里注意是left = mid，而不是left = mid+0.01。例如求1.25和1.5的中间值结果为1.375，由于精确度他已经使mid偏移而不是完全落在nums数组的某个节点上，因此这里不需要再让mid+0.01。

![9d595cb8689f32a06e6c44229eed01b5.png][]

再看一下退出条件当left与right之间的差值小于精确度0.01时，left和right都无处可以移动，也就意味着根号二的结果值在1.41和1.42之间。按照题目要求的精确度0.01，可以直接返回left所指向的值。

**第三步**：根据示意图完善模板代码

func sqrt(n float64) float64 {
      var left float64 = 0
      var right float64 = n
      //当right与left之间的差<=0.01时可以终止寻值
      for right-left > 0.01 {
        mid := (left + right) / 2
        if mid*mid < n {
          left = mid  //注意
        } else if mid*mid == n {
          return mid
        } else if mid*mid > n {
          right = mid  //注意
        }
      }
      //将精确度以外的值去除
      temp := int(left * 100)
      left = float64(temp) / 100
      return left
    }

边界值二分

面试官：那来看这道题你会不会？

![4a506401c30fb79f1f156e086fca7e1a.png][]

考点：**旋转数组**

超超：这题是局部有序数组，要求是寻找数组中的最小值。同样满足二分法的**有序性**和**查找特定元素**俩个必要条件。（：那就按步骤办事呗！

**第一步**：写出二分法模板

**第二步**：画出示意图，确定left，right移动条件，以及最小数字target判断方法

![8e7580b5241620c1b7b0d57fcb31f3c8.png][]

如果数组经过旋转，那么旋转点是唯一个使得nums\[mid\]满足nums\[mid\] < nums\[mid-1\]或nums\[mid+1\] < nums\[mid\]的位置，在图中为nums\[4\] < nums\[3\]。

如果数组未经过旋转，那么target为数组的第一个元素nums\[0\]。

![33929d73ca7366396cee0aaa6fe18f9a.png][]

局部有序数组，先看数组的特点是什么。如果以旋转点为界分为左右俩个区间，4是左边区间的最小值，2是右边区间的最大值，那么**当nums\[mid\] < nums\[0\]则属于右区间，当nums\[mid\] > nums\[len(nums)-1\]则属于左区间。**

**第三步**：根据示意图完善模板代码

func findMin(nums []int) int {
      //初始化游标
      left := 0
      right := len(nums) - 1
      //未寻转或数组长度为1，则返回nums[0]
      if nums[left] < nums[right] {
        return nums[left]
      } else if right == 0 {
        return nums[left]
      }
      
      for left <= right {
        mid := (left + right) >> 1
        //找到旋转点则返回旋转点
        if nums[mid] > nums[mid+1] {
          return nums[mid+1]
        } else if nums[mid] < nums[mid-1] {
          return nums[mid]
        } else if nums[mid] < nums[0] {
          right = mid - 1
        } else if nums[mid] > nums[len(nums)-1] {
          left = mid + 1
        }
      }
      return nums[left]
    }

面试官：看来你对二分还挺熟悉的，那我们来问一些计算机网络的知识吧。

超超：好的（：终于来到了八股文时间????

未完待续～

[1be7db7ac5cceee03fd9b9d8799c460e.png]: /images/20220829/7e07572190554c20aa54e17c18fef84e.png
[7bb678623557068f4599b0270dd215fe.png]: /images/20220829/ad2cd2e9ce324efea9af0f02c55a6088.png
[4a8d759420d91bc51011291a6259a0c6.png]: /images/20220829/79b85717a878497282595ee6ec87378d.png
[9d595cb8689f32a06e6c44229eed01b5.png]: /images/20220829/01e7d62c576d4e2383b8c7d6a1ba4cdb.png
[4a506401c30fb79f1f156e086fca7e1a.png]: /images/20220829/06da50de4c744c40a361897de0387a5b.png
[8e7580b5241620c1b7b0d57fcb31f3c8.png]: /images/20220829/60eb9b46da5840549b3fdee3e93ed2e5.png
[33929d73ca7366396cee0aaa6fe18f9a.png]: /images/20220829/e86caeae9ad34c71bf566711454d2bb9.png