上篇说到超超早经历面试官关于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变化

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

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]中查找开方数了。确定满足二分法的有序性和查找特定元素俩个必要条件后，接着按步骤解题即可。

第一步：写出二分法模板

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变化(节约空间这里省去用不上的节点)

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

再看一下退出条件当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}

边界值二分

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

考点：旋转数组

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

第一步：写出二分法模板

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}

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

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

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

局部有序数组，先看数组的特点是什么。如果以旋转点为界分为左右俩个区间，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]}

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

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

未完待续～