1.特点
细节多，不好写，容易死循环->掌握之后编程最简单的算法
2.学习中的侧重点
1.算法原理
数组有一个规律，他们就可以使用二分的情况,两段性(通过一个规律，发现可以把数组分成两部分）
2.模版
不去死记硬背->理解后再记忆。
1.朴素的二分->最简单->有局限性
2.查找左边界的二分模版 查找右边界的二分模版
万能且好用，细节多
力扣704.二分查找
太简单了，懒得写题解啦
class Solution { public int search(int[] nums, int target) { int begin=0; int end=nums.length-1; int med; for(int i=0;i<nums.length;i++){ med=(begin+end)/2; if(nums[med]==target){ return med; } if(nums[med]<target){ begin=med+1;} if(nums[med]>target){ end=med-1;} } return -1; } }
class Solution { public static int search(int[] nums, int target) { int begin=0; int end=nums.length-1; int med; //没啥大必要，但是也可以这么做 for(int i=0;i<nums.length;i++){ //begin和end，看谁大谁小，假如begin>end那就说明不可以 if(begin>end){ return -1; } //防止越界 med=begin+(end-begin)/2; if(nums[med]==target){ return med; } if(nums[med]<target){ begin=med+1;} if(nums[med]>target){ end=med-1;} } return -1; } }
力扣34.排序数组中查找元素的第一个和最后一个位置
普通的朴素二分：
假如说是33333，这个例子，我用二分也不清楚他的起始位置和结束位置，还是要往回找，这就和暴力大差不差了
二分本质：二段性
1.查找区间左端点【左边小于t,右边大于t】
细节处理：循环条件，left<right,为什么不是left<=right
首先 
class Solution { public int[] searchRange(int[] nums, int target) { //处理边界情况 int []ret=new int[2]; ret[0]=-1; ret[1]=-1; if(nums.length==0){ return ret; } int left=0; int right=nums.length-1; while(left<right){ //求左端点的操作 int mid=left+(right-left)/2; if(nums[mid]<target){ left=mid+1; } else{ right=mid; } } if(nums[left]!=target)return ret; ret[0]=left; //二分右端点 //left可以直接从左端点开始 left=right; right=nums.length-1; while(left<right){ int mid=left+(right-left+1)/2; if(nums[mid]<=target){ left=mid; } else{ right=mid-1; } } ret[1]=right; return ret; } }
力扣69.x的平方根
这题的本质暴力枚举：
把从1到x的数字平方求一遍，因为有顺序，所以使用二分查找
注意这里细节在于mid*mid假如说是小于，等于的话，
这么画图的原因，我们划分的是要求和放在一起，小于和等于都是我们要求的，所以他们是放在一起
让left变到mid这里，中间数分平方可以落在小于，因为mid平方有可能正好等于x
class Solution { public int mySqrt(int x) { if(x<1){ return 0; } long left=1; long right=x; while(left<right){ long mid=left+(right-left+1)/2; if(mid*mid<=x){ left=mid; }else{ right=mid-1; } } return (int)left; } }
力扣35.搜索插入位置
首先他这个插入位置，我们要发现，假如说不是正好,数组里面没有这个数的话，那么nums的target，比他大的那个值的下标，就是他要插入的下标
方法一：同种思想（这个是来以小于等于为一段，大于为一段的，然后有一个特列，假如说小于等于的情况就是0，不然就是小于等于的下一个
public static int searchInsert(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<right){ int mid=left+(right-left+1)/2; if(nums[mid]>target){ right=mid-1; }else { left=mid; } if(nums[mid]==target){ return mid; } } if(nums[0]>=target){ return 0; } return left+1; }
方法2:以小于和大于等于为两段。（也是需要特殊判定，假如那个target很大，如何处理）
class Solution { public static int searchInsert(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<right){ int mid=left+(right-left)/2; if(nums[mid]<target){ left=mid+1; }else { right=mid; } } //特殊判定 if(nums[left]<target){ return left+1; } return left; } }
