大家好，我是 17
写二分的时候，不要每次都重新写，而是记住一个模板，每次都用这个模板。这样做的好处是不容易出错，而且速度快，特别适合面试。
function binarySearch(nums, target) { let low=0,high=nums.length while(low<high){ let mid=low+((high-low)>>1) if(nums[mid]>=target) high=mid else low=mid+1 } return low }; 复制代码
| 输入 | 输出 |
| [ 1，2，2，4 ] , 2 | 1 |
| [ 1，2，2，4 ] , 4 | 4 |
| [ 1，2，2，4 ] , 3 | 3 |
| [ 1，2，2，4 ] , 0 | 0 |
把模板当作一个黑盒，熟记什么样的输入会有什么样的输出。
如果 nums 是升序
- 如果 target 存在，一定会找到，如果有相同值，命中最左边的位置
- 如果不存在，会命中 比 target 略大的值
- 如果 target 大于所有值，会超出最右边界
low == nums.length - 如果 target 小于所胡值,
low == 0
总的来说，就两条，如果 target 存在，命中最左置，如果不存在，命中偏右位置（如果 target 存在，相比于 target的位置）
(high-low)>>1 等价于 Math.floor((high-low)/2)，如果你不习惯于移位的写法，也可以这么写。
要这么写low+ Math.floor((high-low)/2)而不是 Math.floor((high+low)/2) 是因为 high+low可能会溢出,超出 数字的最大表示范围。
[low,high) 左闭右开，也就是说，high的位置比可以取到的位置 加 1,一定要记住。
熟记上面的模板后，我们先练练手。
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
解题：这是最简单的二分查找题目，直接用模板即可。如果目标值存在，则一定能找到。
var search = function(nums, target) { let low=0,high=nums.length while(low<high){ let mid=low+((high-low)>>1) if(nums[mid]>=target) high=mid else low=mid+1 } return nums[low]===target?nums[low]:-1 }; 复制代码
给定一个按升序排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
解题：根据模板特性 第1条，目标值存在则一定找到，并可以返回索引。如果不存在，根据模板特性 第2条 ，返回 比 target 略大的值，正好是插入的位置。代码和模板一模一样。
var searchInsert = function(nums, target) { let low=0,high=nums.length while(low<high){ let mid=low+((high-low)>>1) if(nums[mid]>=target) high=mid else low=mid+1 } return low }; 复制代码
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
解题：可以认为是 从 大于等于1 到 小于等于 num 的数中，看看能不能选出一个数 x x * x = num 如果存在，根据 模板特性1 一定会找到，如果不存在 ，根据特性2 ，会命中一个稍大的数。根据左闭右开的原则，low = 1 ，1是可以取到的最小值，high=num+1 num是可以取到的最大值
var isPerfectSquare = function (num) { let low = 1, high = num + 1 while (low < high) { let mid = low + ((high - low) >> 1) if (mid * mid >= num) high = mid else low = mid + 1 } return low * low == num }; 复制代码
接下来，自己到 leetcode 上面找几道简单题练习一下，切记用模板，只能修改两个地方，其它地方都不要修改。
nums[mid]>=target 这个判断是可以修改的，这也查为什么二分查找不适合成一个通用方法的原因
return low 返回值这里 根据题意 灵活修改。
如果 nums里面有重复数，模板是命中最左边的位置 ，如果想要命中最右边的位置
nums[mid]>target ... return low-1 复制代码
如果你都顺利通过了，说明你已经掌握了模板，可以尝试些复杂些的题目了。这些题目的关键在于如何找到二分的条件。
题解：最小值一定在两段有序数组的交界偏右的位置。如果中值比nums[0]小，说明交界一定在左侧，否则在右侧。 根据 模板 特性1 如果 交界 存在，则一定找到 。如果交界不存在，也就是 数组整个有序，那么 nums[mid]<nums[0] 永远为假，high 最后的结果 就是 nums.length,low 的退出条件是 等于 high,low == nums.length
var findMin = function(nums) { let low=0,high=nums.length while(low<high){ let mid=low+((high-low)>>1) if(nums[mid]<nums[0]) high=mid else low=mid+1 } return nums[low]?? nums[0] }; 复制代码
题解：用模板可以找到最左面的位置，最右边的位置可以用 前面讲到的
nums[mid]>target ... return low-1 复制代码
var searchRange = function(nums, target) { let low=0,high=nums.length; let ans=[] while(low<high){ let mid=low+((high-low)>>1) if(nums[mid]>=target) high=mid else low=mid+1 } if(nums[low]!==target) return [-1,-1] ans[0]=low high=nums.length while(low<high){ let mid=low+((high-low)>>1) if(nums[mid]>target) high=mid else low=mid+1 } ans[1]=low-1 return ans }; 复制代码
把上面提到的都熟记后，找几道题练练，二分的基本功就差不多了
