1. 整体说明
二分查找是基本的、常见的算法，大家徒手写应该不成问题。面试中经常出现,特别是面试官想给你送分的时候。但大多数时候大家的二分查找写法其实在面试官看来仅仅是及格。
大家可能会想，二分查找能玩出什么花样来？今天，咱们一起来看。
本文知识要求：会看图，会识字。
2. 最简单的二分查找
【你真的懂二分查找吗】话不多说，直接看leetcode 原题。leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。下面是最常见的实现版本，我们后续称之为版本A.
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-search
func searchA(nums []int, target int) int {lo, hi := 0, len(nums) // 在左闭右开区间[lo, hi) 查找target
var mid int
var midVal int
for lo < hi { // 最后退出时，[lo,hi）区间为空
mid = (lo + hi) / 2 // 中间索引
midVal = nums[mid]
if midVal == target {
return mid
} else if target < midVal {
hi = mid
} else { // midVal < target
lo = lo + 1
}
}return -1
}3. 这么简单的算法还能优化吗？ 该算法时间复杂度为O(Nlogn), n为数组长度，N为系数。我们的目标是：能否让N 小一些。
我们看上面的版本A实现，发现每次循环中，通过 nums[mid] ，经过2次比较，将数组分为三部分。如下图所示。
文章图片
其实，我们可以将nums[mid] 和nums[mid+1, hi) 合并为一个区间，这个区间的元素满足 >= target。这样做的目的是将比较次数优化为1.
退出区间时，hi = lo+1, 区间[lo,hi)仅有一个元素
文章图片
(可能会对这个优化的意义产生疑问。如果我们的数组不是整数，而是长字符串呢？)
1次比较，划分为2个区间示意图。
此时算法实现如下，我们称之为版本B。
func searchB(nums []int, target int) int {lo, hi := 0, len(nums) // 在左闭右开区间[lo, hi) 查找target
var mid int
var midVal int
for 1 < hi-lo { // 最后退出时，[lo,hi）区间仅有一个元素
mid = (lo + hi) / 2 // 中间索引
midVal = nums[mid]
if target < midVal {
hi = mid
} else { // midVal <= target
lo = lo + 1
}
}if nums[lo] == target {
return lo
}return -1
}4. 打动面试官 <1> 如果数组中有目标元素重复，能否返回最后面的索引
比如要删除数组中一个目标元素，删除最后位置的目标元素，数组移动最小
<2> 如果数组中没有目标元素，能否返回可以插入的索引，而不是简单的-1
这个位置从语义上说是：小于target 的最后一个元素的下一个位置
这两个问题对我们的返回值提出了更高的要求。好难啊？！不要怕，其实思路我们之前已经见过了。
关键点在于退出时lo,hi的语义(lo=hi, 且lo为符合要求位置的后面一个位置)
文章图片
func searchC(nums []int, target int) int {lo, hi := 0, len(nums) // 在左闭右开区间[lo, hi) 查找target
var mid int
var midVal int
for 0 < hi-lo { // 最后退出时，[lo,hi）区间为空
mid = (lo + hi) / 2 // 中间索引
midVal = nums[mid]
if target < midVal {
hi = mid
} else { //midVal <= target
lo = mid + 1
}
}return lo - 1
}
