二分查找——简单正确模板（打破传统思维，真的简单易懂！）

B站课程链接：二分查找为什么总是写错？_哔哩哔哩_bilibili

注：以下为课程截屏及总结

伪代码

 划分为红蓝两块

即要找的元素在红蓝边界处，边界左右两边的红蓝块可以被排除

ps：原本都为黑的，通过二分查找来分别拓展红蓝区域

算法的细节问题（正确性证明）

 边界值举例说明算法 

 算法模板流程

 举例代码

public class Solution {public int binSearch(int a[], int target) {int low = -1, height = a.length;  //注意设置为下限的下一个数，和上限的上一个数while (low + 1 != height) {       //通用终止条件int mid = low + (height - low) / 2;if (a[mid] == target) {return mid;} else if (a[mid] < target) {low = mid;} else if (a[mid] > target) {height = mid;}}// 返回的比给定值大的下标// 如数组a为：1 2 4 5，查找3，返回的则是下标2（a[2]=4>3>2）// 即红色区域的下限// 同理也可返回low，即蓝色区域上限。根据具体需求决定返回值。return height;}
}

算法题目应用

例题：287. 寻找重复数 - 力扣（Leetcode）

代码：

public class Solution {public int findDuplicate(int[] nums) {int[] temp = Arrays.copyOf(nums, nums.length);Arrays.sort(temp);for (int i = 0; i < nums.length; i++) {if (binSearch_firstBiggerandEqual(temp, nums[i]) != binSearch_lastBiggerandEqual(temp, nums[i])) {return nums[i];}}return -1;}//找第一个>=target的下标public int binSearch_firstBiggerandEqual(int[] nums, int target) {int left = -1, right = nums.length;int mid;while (left + 1 != right) {mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid;} else if (nums[mid] >= target) {right = mid;}}return right;}//找最后一个>=target的下标public int binSearch_lastBiggerandEqual(int[] nums, int target) {int left = -1, right = nums.length;int mid;while (left + 1 != right) {mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid;} else if (nums[mid] > target) {right = mid;}}return left;}
}