力扣刷题-数组-二分查找总结

前言

二分查找的使用前提/一般何时想到使用二分查找：数组为有序数组、数组中重复元素（因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的）
二分查找的关键 / 不容易写混乱的关键 / 谨记的不变量：区间定义不变量——要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
区间定义分类：区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)

二分法第一种写法

二分法第二种写法

题目

704 二分查找

（简单，二分查找基础！）
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
这题是最基础的二分查找题目，没有变形，采用二分查找方法做即可，需注意循环不变量。

35 搜索插入位置

（简单，二分查找基础！）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
这题算是二分查找的一个变型，就是当存在目标值的时候，返回索引。但不存在目标值的时候，返回的不是704题中的-1，而是要返回被顺序插入的位置。跳出来想一想，现在是找不到位置（例如：2 3 5 6，目标值是4），要找插入位置，当找不到，是破坏循环条件：left<=right，现在right到left左边了，刚好right+1就是目标值位置，所以插入位置就应该是right+1

34 在排序数组中查找元素的第一个和最后一个位置

（中等，二分查找进阶）
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
这题算是二分查找的进阶，因为在数组中元素已经不重复，目标值可能有多个，有开始位置和结束位置，这就要分析一下了：

所以关键是去寻找左右边界！——> 采用二分法来去寻找左右边界，为分别写两个二分来寻找左边界和右边界。
关键：循环不变量 + 计算出来的右边界（left = mid + 1; right_border = left）是不包含target的右边界，左边界（right = mid - 1; left_border = right）同理

参考：https://programmercarl.com/