1. 整体阐明
二分查找是根本的、常见的算法，大家徒手写应该不成问题。面试中经常出现, 特地是面试官想给你送分的时候。但大多数时候大家的二分查找写法其实在面试官看来仅仅是及格。
大家可能会想，二分查找能玩出什么花色来？明天，咱们一起来看。
本文常识要求：会看图，会识字。
2. 最简略的二分查找
话不多说，间接看 leetcode 原题。leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 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
上面是最常见的实现版本，咱们后续称之为版本 A.
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
}