一分为二,化繁为简
思路 
预处理–数组有序,不是有序则 先排序 
二分查找–将数组一分为二 
后处理–剩余一半数组中查找可行的范围 
 
三个模板 
模板一 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 int  binarySerach1 (int [] nums, int  target)  if  (nums == null || nums.length == 0 ) {return  -1 ;int  left = 0 , right = nums.length - 1 ;while  (left <= right) {int  mid = left + (right - left) / 2 ;if  (nums[mid] == target) {return  mid;else  if  (nums[mid] > target) {1 ;else  {1 ;return  -1 ;
X的平方根 题目 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
解题思路 找x的平方根,其实就是找一个使n * n <= x 成立的最大的 n。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int  MySqrt1 (int  x) int  left = 0 , right = x;int  ans = -1 ;while (left <= right){int  mid = (right - left) / 2  + left;if (mid * mid <= x){1 ;else {1 ;return  ans;
模板二 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 int  binarySearch2 (int [] nums, int  target)  if  (nums == null || nums.length == 0 )return  -1 ;int  left = 0 , right = nums.length;while  (left < right) {int  mid = left + (right - left) / 2 ;if  (nums[mid] == target) {return  mid;else  if  (nums[mid] < target) {1 ;else  {if  (left != nums.length && nums[left] == target) return  left;return  -1 ;
X的平方根 [left,right)解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int  MaSqrt2 (int  x) int  left = 0 , right = x + 1 ;int  ans = -1 ;while (l < r){int  mid = (right - left) / 2  + left;if (mid * mid <= x){1 ;else {return  ans;
模板三 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 int  binarySearch3 (int [] nums, int  target)  if  (nums == null || nums.length == 0 )return  -1 ;int  left = 0 , right = nums.length - 1 ;while  (left + 1  < right) {int  mid = left + (right - left) / 2 ;if  (nums[mid] == target) {return  mid;else  if  (nums[mid] < target) {else  {if  (nums[left] == target) return  left;if  (nums[right] == target) return  right;return  -1 ;
X的平方根 (left,right)解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int  MySqrt3 (int  x) int  left = -1 , right = x + 1 ;int  ans = -1 ;while (left + 1  < right){int  mid = (right - left) / 2  + left;if (mid * mid <= x){else {return  ans;
区别 
初始边界left和right不同 
while()内判断条件不同left和right后处理的不同 
 
首先明白我们二分搜索的区间是怎么划分的。
初始化边界 
如果是[left,right],那么left = 0,right = nums.size() - 1。这样刚好包含nums数组全部数组,如果right = nums.size(),则多包含了一个数组外的数
如果是[left,right),那么left = 0,right = nums.size()。跟[]不同,right = nums.size()时才能刚好把数组包含,如果right = nums.size() - 1,则会少一个右边界元素。
如果使(left,right),那么left = -1,right = nums.size()。
 
while内判断条件 不断将区间一分为二,当出现不合法的区间时中断循环。
[left,right],只需要判断条件合法即可,left <= right情况可能出现,如果选择left < right则少了一个循环 
[left,right),不可能出现left = right,因此left< right即可决定循环是否中止 
(left,right),left 也不能使用left 与 right是否相等来中止循环,当left - 1 = right(此情况不存在)时就需要中止循环 
 
left right后处理 根据区间类型看mid是否在二分后的区间内来决定后处理。
[left,right]
mid < target,如果left = mid,划分后的区间仍然包含已经进行判断过的mid,因此应该为mid + 1。mid > target,如果right = mid,划分后的区间仍然包含…mid = target,找到结果,返回 
 
[left,right)
mid < target,left = mid即可满足划分后的区间不包含判断过的mid(右开)mid > target,left = mid + 1,同左闭mid = target,不会有这种情景,在left - 1 = right循环就中止了 
 
(left,right)
mid < target,left = midmid > target,right = midmid = target,不会有这种情景,在left - 1 = right循环就中止了 
 
 
总结 对于不同的问题,以上三种模板其实都可以使用,不过是实现方法的不同而已。对于不同的问题选择不同的模板可以有助于代码的理解与实现。
例题 搜索插入的位置 题目 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class  Solution  {public :int  searchInsert (vector<int >& nums, int  target)  int  l = 0 , r = nums.size () - 1 ;while (l <= r){int  mid = (r - l) / 2  + l;if (nums[mid] < target){1 ;else {1 ;return  l;
这个代码是抄的别人的,自己写的巨麻烦😫。
总结 该题相当于找最后一个小于target的下一个下标(或者说第一个大于或等于target的数组值的下标),随着循环进行,l代表的是最后一个小于target的下一个下标,而r代表的是第一个大于等于target的数组值的上一个下标 ,我们要返回的是最后一个小于target的下一个下标,即l。
对于题目要求的结果,我们要分析并总结出其对应的编程语言,并理解left,right对应的是什么。
在排序数组中查找元素的第一个和最后一个位置 题目 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。
思路一 根据二分特性,随着循环进行,l代表的是最后一个小于target的下一个下标,而r代表的是大于等于target的上一个下标,而本题要求第一个和最后一个元素位置,因此可以使用两次二分,分别找第一个最后一个。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 vector<int > searchRange (vector<int >& nums, int  target)   {int  l = 0 , r = nums.size () - 1 ;int  first = -1 , last = -1 ;while  (l <= r) {int  mid = (l + r) / 2 ;if  (nums[mid] == target) {1 ; else  if  (nums[mid] > target) {1 ;else  {1 ;0 ;size () - 1 ;while  (l <= r) {int  mid = (l + r) / 2 ;if  (nums[mid] == target) {1 ; else  if  (nums[mid] > target) {1 ;else  {1 ;return  vector<int >{first, last};
总结 还是要使用相等这一利器,不能为了用之前的方法而硬解。此题会有找不到的情况,可能越界,必须使用相等。
思路二 当找到target时,将l和r缩小,直到nums[l]和nums[r]都等于target,然后返回
当找不到target时,循环终止,直接返回{ -1, -1}
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 vector<int > searchRange (vector<int >& nums, int  target)   {int  l = 0 , r = nums.size () - 1 ;while  (l <= r) {int  mid = (r - l) / 2  + l;if  (nums[mid] < target) {1 ;else  if  (nums[mid] > target) {1 ;else  {while  (nums[l] != target) {while  (nums[r] != target) {return  vector<int >{l,r};return  {-1 ,-1 };
搜索旋转排序数组 题目 整数数组 nums 按升序排列,数组中的值 互不相同  。nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始  计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。旋转后  的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
代码 回想二分搜索的思想,一分为二,化繁为简!
对于旋转后的数组,一分为二后一定有一半是有序的,另一半无序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 int  search (vector<int >& nums, int  target)  int  l = 0 , r = nums.size () -1 ;while  (l <= r)int  mid = (l + r) >> 1 ;if  (target == nums[mid]) return  mid;if  (nums[l] <= nums[mid])if  (target >= nums[l] && target < nums[mid])-1 ;else 1 ;else if  (target > nums[mid] && target <= nums[r])1 ;else -1 ;return  -1 ;
总结 寻找旋转排序数组中的最小值 题目 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到: [4,5,6,7,0,1,2] [0,1,2,4,5,6,7] [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
代码 题目转换一下思路,其实就是找到最后一个小于ans初始值的数(用到向上取整)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int  findMin (vector<int >& nums)  int  ans = nums[0 ];int  l = 0 , r = nums.size () - 1 ;while (l <= r){int  m = (r - l + 1 ) / 2  + l;if (nums[l] < nums[m]){if (nums[l] < ans){1 ;else {if (nums[m] < ans){1 ;return  ans;
总结 向上取整在搜索最后一个满足条件时使用。