【二分搜索】二分搜索代码模板
下面这首算法小诗出自《labuladong的算法小抄》
二分搜索套路歌
二分搜索不好记，左右边界让人迷。小于等于变小于，mid加一又减一。
就算这样还没完，return应否再减一？信心满满刷力扣，通过比率二十一。
我本将心向明月，奈何明月照沟渠！labuladong从天降，一同手撕算法题。
管它左侧还右侧，搜索区间定乾坤。搜索一个元素时，搜索区间两端闭。
while条件带等号，否则需要打补丁。if相等就返回，其他的事甭操心。
mid必须加减一，因为区间两端闭。while结束就凉凉，凄凄惨惨返-1.
搜索左右边界时，搜索区间要阐明。左闭右开最常见，其余逻辑便自明：
while要用小于号，这样才能不漏掉。if相等别返回，利用mid锁边界。
mid加一或减一？要看区间开或闭。while结束不算完，因为你还没返回。
索引可能出边界，if检查保平安。左闭右开最常见，难道常见就合理？
labuladong不信邪，偏要改成两端闭。搜索区间记于心，或开或闭有何异？
二分搜索三变体，逻辑统一容易记。一套框架改两行，胜过千言和万语。
二分搜索框架
先写一个二分搜索的框架，后面的几种二分搜索的变形都是基于这个代码框架：
public int binarySearch(int[] nums, int target) {int left = 0, right = ...;int counter = 1;while (...) {int mid = left + (right - left) / 2;System.out.println("搜索了" + counter + "次,left = " + left + ",right = " + right + ",mid = " + mid);++counter;if (nums[mid] == target) {...} else if (nums[mid] > target) {right = ...;} else if (nums[mid] < target) {left = ...;}}return ...;}分析二分搜索的一个技巧是：不要出现 else,，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。其中 ... 标记的地方，就是可能出现细节问题的地方，当你看到一个二分搜索的代码时，首先要注意这几个地方。
另外声明一下，计算 mid 时需要防止溢出。代码中 left + (right - left) / 2 和 (left + right) / 2 的结果相同。但是如果 left 和 right 太大，直接相加会导致整型溢出，而改写成前者则不会出现溢出。
寻找一个数（基本的二分搜索）
这个场景最简单：搜索一个数，如果存在，则返回其索引，否则返回-1。
public int binarySearch(int[] nums, int target) {int left = 0, right = nums.length - 1; // 注意int counter = 1;while (left <= right) {int mid = left + (right - left) / 2;System.out.println("搜索了" + counter + "次,left = " + left + ",right = " + right + ",mid = " + mid);++counter;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {right = mid - 1; // 注意} else if (nums[mid] < target) {left = mid + 1; // 注意}}return -1;}1.为什么 while 循环的条件中是 <=，而不是 <？
答：因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。这二者可能出现在不同功能的二分搜索中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。这个算法中使用的是前者 [left, right]，两端都闭的区间。这个区间其实就是每次进行搜索的区间。while (left < right) 的终止条件是 left == right，写成区间的形式就是 [left, right]，带个具体的数字进去，即 [2, 2]，这个时候区间非空，还有一个数2，但此时 while 循环终止了。也就是说，区间 [2, 2] 被漏掉了，索引2没有被搜索，如果这时候直接返回-1，可能是错误的。
2.为什么 left = mid + 1，right = mid - 1？有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？
答：刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。如果发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。
3.该算法有什么缺陷？
答：这个算法存在局限性。比如，提供的是有序数组 nums = [1,3,3,3,4]，target = 3，此算法返回的是正中间的索引2。但是如果我想得到 target 的左侧边界，即索引1，或者想得到 target 的右侧边界，即索引3，则算法是无法处理的。这样的需求很常见，但有人也许会说，找到一个 target，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分搜索对数级的复杂度了。
寻找左边界的二分搜索
举个该场景的例子：给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
完整代码：
public int leftBound(int[] nums, int target) {int left = 0, right = nums.length - 1;int counter = 1;// 搜索区间为 [left, right]while (left <= right) { int mid = left + (right - left) / 2;System.out.println("搜索了" + counter + "次,left = " + left + ",right = " + right + ",mid = " + mid);++counter;if (nums[mid] < target) {left = mid + 1; // 搜索区间为 [mid + 1, right]} else if (nums[mid] > target) {right = mid - 1; // 搜索区间为 [left, mid - 1] } else if (nums[mid] == target) {right = mid - 1; // 收缩右侧边界}}// 检查出界情况/*if (left >= nums.length || nums[left] != target) {return -1;}*/return left;}寻找右侧边界的二分搜索
public int rightBound(int[] nums, int target) {int left = 0, right = nums.length - 1;int counter = 1;// 搜索区间为 [left, right]while (left <= right) {int mid = left + (right - left) / 2;System.out.println("搜索了" + counter + "次,left = " + left + ",right = " + right + ",mid = " + mid);++counter;if (nums[mid] < target) {left = mid + 1; // 搜索区间为 [mid + 1, right]} else if (nums[mid] > target) {right = mid - 1; // 搜索区间为 [left, mid - 1]} else if (nums[mid] == target) {left = mid + 1; // 收缩左侧边界}}// 检查出界情况/*if (right < 0 || nums[right] != target) {return -1;}*/return right;}