前言
二分查找是一种在有序数组中查找某一特定元素的搜索算法，在很多人的印象里，二分查找是一种比较简单的算法，然而在实际做题中，二分查找经常容易写错，特别是在处理边界条件的时候，今天我们就来聊一聊二分查找，看能不能找到一种比较简单，通用的方法来解决大部分的二分查找问题
先看一个例子
先给定一个数组
<pre class="cm-s-default" style="color:rgb( 24 , 24 , 24 );margin:0px;padding:0px;background:none 0% 0% / auto repeat scroll padding-box border-box rgba( 0 , 0 , 0 , 0 )">const list = [1, 2, 3, 5, 5, 5, 8, 9]
复制代码</pre>
思考下面4个问题
先简单想想来看下答案
以上其实就是我们在使用2分查找时经常会遇到的各种边界问题，而对于边界问题的处理，常常决定着最终结果的准确
如何分析问题
对于二分查找的问题，都可以抽象为在一个有序数组中寻找边界，以下以寻找蓝，红方块边界为例，最开始拿到数组是白色的二分查找算法 java，通过一次又一次的查找，去扩大蓝色 (左指针右移 left + 1) 和红色区域 (右指针左移 right - 1)二分查找算法 java 【算法入门】二分查找，最终找到边界 （即求出未知数K）
解题模板
大家来看一段伪代码
<pre class="cm-s-default" style="color:rgb( 24 , 24 , 24 );margin:0px;padding:0px;background:none 0% 0% / auto repeat scroll padding-box border-box rgba( 0 , 0 , 0 , 0 )">left = -1, right = n
while left + 1 != right
m = (left + right) / 2
if IsBlue(m)
left = m
else
right = m
return left or right
复制代码</pre>
做一道 题
704. 二分查找 - 力扣（）
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 ，写一个函数搜索 nums 中的 ，如果目标值存在返回下标二分查找算法 java，否则返回 -1。
分析
二分查找都可以看做找边界 的问题，本题 left 左区域的值都小于 (即蓝色区域) ，右边界的值都大于 (即红色区域) ，而等于时即求出边界
解题
<pre class="cm-s-default" style="color:rgb( 24 , 24 , 24 );margin:0px;padding:0px;background:none 0% 0% / auto repeat scroll padding-box border-box rgba( 0 , 0 , 0 , 0 )">/**
- @param {number[]} nums
- @param {number} target
- @return {number}
*/
<p>
var search = function(nums, target) {
let left = -1
let right = nums.length
while(left + 1 != right) {
let middle = (left + right) >> 1 // 使用 >> 位运算代替除法避免小数
if (nums[middle] == target) {
return middle
}
if (nums[middle] > target) { 
right = middle
}
if (nums[middle] < target) {
left = middle
}
}
return -1 };
复制代码</pre></p>
怎么样，大家可以试试用这个解题模板去试试，看是否能让你做二分查找相关的题目时准确率更高些 ^-^