二分查找的快速上手二分查找的算法我们肯定不少见那我们最重要的是要分析什么呢我们最重要的就是需要分析出来left跟right应该怎么移动是具体移动到mid的本身上还是mid-1或者是mid1这个是要汇总点考虑的考虑完之后mid的写法就可以确定了是要向上取整还是向下取整二分查找的边界更新mid的常用写法left midleft (right - left 1) / 2left mid 1left (right - left) / 2一x的平方根题目解析这题我们依旧使用的是二分查找的方法我们通过定义left跟right两个指针并且left指向1right指向x我们找到中间值然后判断中间值的平方跟x的大小比较如果大了那么我们要求的数值就在left到mid-1的区间rightmid-1如果小于等于的话我们要求的值就在mid到right的区间leftmid然后重复这样的操作直到最后剩两个值也就是循环中leftright这样的条件的最后一步然后最后我们返回left跟right其中的一个就行这里我们要注意的是中间值的求法这里我们需要加1也就是leftright-left1/2这样的求法避免死循环举个例子假设我们最后剩余4跟5不加1的求法求出来是4也就是向下取整如果这个时候是小于等于这个选项那我们的left就不会变也就是说left跟right永远没办法相遇当然这里判断中间值是否要加1记住这个规律就行二分查找的边界更新mid的常用写法left midleft (right - left 1) / 2left mid 1left (right - left) / 2代码演示public int mySqrt(int x) { if (x1){ return 0; } long left1,rightx; while (leftright){ long midleft(right-left1)/2; if (mid*midx){ leftmid; }else { rightmid-1; } } return (int) left; }二搜索插入位置题目解析这题我们依旧先分析left跟right具体怎么挪动对于这题我们首先需要找到的就是刚刚好大于t的那一个值的下标也就是说我们将数组分为小于t以及大于等于t的部分注意这里的分区域我们需要大于等于t的那个下标所以区域也分一部分为大于等于t的也就是说当midtleft得挪动因为我们需要找的是刚刚好大于t的那个数所以mid这个数的下标肯定不是我们要的left肯定不能直接到mid而是到mid1的位置leftmid1当midtrightmid代码演示public int searchInsert(int[] nums, int target) { int left0,rightnums.length-1; while (leftright){ int midleft(right-left)/2; if (nums[mid]target){ rightmid; }else { leftmid1; } } if (nums[left]target){ return left1; }else return left; }三山脉数组的登峰索引题目解析这题为什么也可以使用二分查找呢原因是这题也可以分为两段一段是左边的底端到峰值一段是峰值加一到右边的底端我们需要找的是大的那一个所以我们需要判断当我们的arr【mid】arr【mid-1】所以左边判断完成并且此时的mid还有可能是我们需要的值所以leftmid当arr【mid】arr【mid-1】我们的rightmid-1代码演示public int peakIndexInMountainArray(int[] arr) { int left0,rightarr.length-1; while (leftright){ int midleft(right-left1)/2; if (arr[mid]arr[mid-1]){ leftmid; }else { rightmid-1; } } return left; }