二分查找
一、什么是二分查找法
二分查找法（Binary Search）是一种在有序数组中查找特定元素的算法。它通过将目标值与数组中间元素进行比较，从而排除掉一半的数据，以实现快速的搜索过程。
二、具体实现步骤
1.确定确定target所在数组的左右边界
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)
左闭右闭
如果我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
那么遍历时的范围就应该是while (left <= right), 要使用 <= ，因为left == right是有意义的
左闭右开
如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right)
那么遍历时的范围就应该是while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
2.取中间值
取数组的中间元素，与目标值进行比较。
左闭右闭
如果我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]。假如说target的值小于数组中间的那个数，也就是if (nums[middle] > target) ，target在数组的左半部分，那么right 要赋值为 middle - 1，因为target肯定比原本的middle值要小，我们不需要再去比较一次i原本middle和target的值了，并且我们是定义的一个闭区间，所以right要赋值给middle-1，也就是说下次我们在[0,middle-1]这个闭区间里面继续找。
左闭右开
如果说定义 target 是在一个在左闭右开的区间里，假如说target的值还是小于数组中间的那个数，也就是if (nums[middle] > target) ，target在数组的左半部分，那么right 要赋值为 middle，因为target肯定比原本的middle值要小，我们也不需要再去比较一次i原本middle和target的值了，并且我们是定义的一个开区间，所以下次我们就在[0,middle)这个区间找。
3.中间元素=目标值
如果中间元素等于目标值，则找到了目标，算法结束。
4.中间元素大于目标值
如果中间元素大于目标值，则目标值只可能在左半部分，因此将搜索范围缩小为左半部分，再次进行二分查找。
5.中间元素小于目标值
如果中间元素小于目标值，则目标值只可能在右半部分，因此将搜索范围缩小为右半部分，再次进行二分查找。
6.重复
重复以上步骤，直到找到目标值或者确定目标值不在数组中。
三、使用条件
数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一。
四、js版本示例
1.左闭右闭
(right - left) >> 1 这个表达式是一个位运算操作。在这里，>> 是右移位运算符，将操作数向右移动指定的位数。
(right - left) 计算了右边界和左边界之间的距离。
>> 1 将这个距离向右移动一位，相当于除以2。这是因为在计算机中，右移一位相当于将数值除以2，并且效率更高。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
let mid, left = 0, right = nums.length - 1;
// 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
while (left <= right) {
// 位运算 + 防止大数溢出
mid = left + ((right - left) >> 1);
// 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；如果右边界更新为mid，那中间数还在下次查找范围内
if (nums[mid] > target) {
right = mid - 1; // 去左面闭区间寻找
} else if (nums[mid] < target) {
left = mid + 1; // 去右面闭区间寻找
} else {
return mid;
}
}
return -1;
};
2.左闭右开
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
// right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间
let mid, left = 0, right = nums.length;
// 当left=right时，由于nums[right]不在查找范围，所以不必包括此情况
while (left < right) {
// 位运算 + 防止大数溢出
mid = left + ((right - left) >> 1);
// 如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应在；
// 由于right本来就不在查找范围内，所以将右边界更新为中间值，如果更新右边界为mid-1则将中间值的前一个值也踢出了下次寻找范围
if (nums[mid] > target) {
right = mid; // 去左区间寻找
} else if (nums[mid] < target) {
left = mid + 1; // 去右区间寻找
} else {
return mid;
}
}
return -1;
};
五、力扣刷题
1.搜索插入位置
这道题在原有的基础上增添了一个新的条件：就是找不到元素时要返回元素本该插入的位置
为什么返回的值变成了right+1呢？
这是因为在循环过程中，我们通过不断更新 left 和 right 来缩小搜索范围，最终使得 left 大于 right。而 right 的值恰好是目标值在数组中最后一个小于目标值的元素的索引。所以，插入位置应该在 right 的右侧，即 right + 1 处。
例如，考虑一个有序数组 [1, 3, 5, 6]，目标值是 4。在二分查找过程中，最终会有 left = 2 和 right = 1，即 right + 1 = 2，这表示目标值 4 应该插入到索引 2 的位置上。
因此，在这段代码中，返回的是 right + 1，表示目标值应该插入的位置。
力扣数组的其他习题将会在后续持续更新打卡……关注收藏不迷路
