二分思想的基本思想：
是将有序数组分成两半，通过比较数组中间元素与目标值大小，来决定下一步搜索的区间是左半部分还是右半部分，然后递归再选定的区间内继续查找。（部分有序的数组也可使用这一思想）
二分查找基础代码
根据划分区间方法的不同，主要分为三种类型(并在代码后方附有注解)：
查找的区间为闭区间[left,right]
public int binarySearch(int[] nums, int target) {
int left= 0;
int right= nums.length - 1;
while (left<= right){//循环的判断条件正好满足[left,right]
//int mid = left+ (right-left) //下面代码可以写成这个可以防止整数相加后的溢出结果
int mid =(right+ left) / 2;
if (nums[mid] < target) {
left= mid + 1; // 在右半部分查找
} else {
right= mid - 1; // 在左半部分查找
}
}
return left; //循环结束之后，left在right的右边，且满足right+1=left找到目标值，返回left(right+1)，若循环结束之后还没找到目标值，这返回-1;
}
查找区间为左开右闭区间[left,right)
public int binarySearch(int[] nums, int target) {
int left= 0;
int right= nums.length;
while (left< right) {//循环的判断条件正好满足[left,right)
int mid = left+ (right- left) / 2;//防止溢出
if (nums[mid] < target) {
left= mid + 1;// 在右半部分查找
} else {
right= mid; // 在左半部分查找
}
}
return left;//返回 left 还是 right 都行，因为循环结束后 left == right，若循环结束之后还没找到目标值，这返回-1;
}
查找区间都为开区间(left, right)
private int lowerBound3(int[] nums, int target) {
int left = -1, right = nums.length;
while (left + 1 < right) { // 满足开区间 (left, right)
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid; // 右半部分查找
} else {
right = mid; //左半部分查找
}
}
return right;//循环最后还是满足(left, right)left《right，right指向最后目标元素。
}
下面找了几个力扣题型进行练习：
二分查找
class Solution {
public int searchInsert(int[] nums, int target) {
int left= 0;
int right= nums.length;
while (left< right) {//循环的判断条件正好满足[left,right)
int mid = left+ (right- left) / 2;//防止溢出
if (nums[mid] < target) {
left= mid + 1;// 在右半部分查找
} else {
right= mid; // 在左半部分查找
}
}
return left;//返回 left 还是 right 都行，因为循环结束后 left == right，若循环结束之后还没找到目标值，这返回-1;
}
}
从上面二分查找基础代码标题任意找一个代码都能解决。
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = binarySearch(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[]{-1, -1};
}
int end = binarySearch(nums, target + 1) - 1;
return new int[]{start, end};
}
public int binarySearch(int[] nums, int target) {
int left= 0;
int right= nums.length - 1;
while (left<= right){//循环的判断条件正好满足[left,right]
//int mid = left+ (right-left) //下面代码可以写成这个可以防止整数相加后的溢出结果
int mid =(right+ left) / 2;
if (nums[mid] < target) {
left= mid + 1; // 在右半部分查找
} else {
right= mid - 1; // 在左半部分查找
}
}
return left; //循环结束之后，left在right的右边，且满足right+1=left找到目标值，返回left(right+1)，若循环结束之后还没找到目标值，这返回-1;
}
}
从题目可以看出有两个target值，用二分查找先找出开始位置之后，在找出结束位置。
2856. 删除数对后的最小数组长度
class Solution {
public int minLengthAfterRemovals(List<Integer> nums) {
int n = nums.size();
int x = nums.get(n / 2);
int maxCnt = lowerBound(nums, x + 1) - lowerBound(nums, x);
return Math.max(maxCnt * 2 - n, n % 2);
}
private int lowerBound(List<Integer> nums, int target) {
int left =0, right = nums.size()-1;
while (left<=right) {
int mid = left + (right - left) / 2;
if (nums.get(mid) < target)
left = mid+1;
else
right = mid-1;
}
return left;
}
}
二分答案：求最小和最小
下面是灵神说的话，挺好理解的
在练习时，请注意「求最小」和「求最大」的二分写法上的区别。
前面的「求最小」和二分查找求「排序数组中某元素的第一个位置」是类似的，按照红蓝染色法，左边是不满足要求的（红色），右边则是满足要求的（蓝色）。
「求最大」的题目则相反，左边是满足要求的（蓝色），右边是不满足要求的（红色）。这会导致二分写法和上面的「求最小」有一些区别。
以开区间二分为例：
求最小：check(mid) == true 时更新 right = mid，反之更新 left = mid，最后返回 right。
求最大：check(mid) == true 时更新 left = mid，反之更新 right = mid，最后返回 left。
对于开区间写法，简单来说 check(mid) == true 时更新的是谁，最后就返回谁。相比其他二分写法，开区间写法不需要思考加一减一等细节，个人推荐使用开区间写二分。
475. 供暖器
// 找出所有房屋距离最近的暖气，即每个房屋距离暖气的最小距离，在所有最小距离中，选取最大值，即为最大半径
// 注： j为什么不重置为0， 重置为0也可通过，但涉及到重复计算，
// 因为都是排序过后的，从小到大，所以，当前house的值，距离暖气都可以达到最小值，
// 往后面的house， 更可以基于此暖气值达到最小值
//先排序，然后给两个指针，按照顺序找到每个屋子距离最近的加热器，记录其位置差
//所有的位置差里面最长的那一个就是最小的加热器半径
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int n = houses.length;
int m = heaters.length;
int minr = 0;
int j = 0;
for (int i = 0; i < n; i++) {
while (j < m - 1 && (Math.abs(heaters[j] - houses[i]) >= Math.abs(heaters[j + 1] - houses[i])))
j++;
minr = Math.max(minr, Math.abs(heaters[j] - houses[i]));
}
return minr;
}
}
这一题没有用二分思想，感觉排序思想容易理解啦！！!
2594. 修车的最少时间
class Solution {
public long repairCars(int[] ranks, int cars) {
int maxRank = Arrays.stream(ranks).max().getAsInt();
long low = 1, high = (long) maxRank * cars * cars;
while (low < high) {
long mid = low + (high - low) / 2;
if (canRepair(ranks, mid, cars)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
public boolean canRepair(int[] ranks, long time, int cars) {
long total = 0;
for (int rank : ranks) {
long count = (long) Math.sqrt(time / rank);
total += count;
if (total >= cars) {
return true;
}
}
return false;
}
}
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int left = 1;
int right = n;
while (left <= right) {
int mid = (left + right)/2;
if (citations[n - mid] >= mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
}
// class Solution {
// public int hIndex(int[] citations) {
// int h=0,i=citations.length-1;
// while(i>=0&&citations[i]>h){
// h++;
// i--;
// }
// return h;
// }
// }
有序想到二分思想，题目含义是找到是否有至少i篇论文引用次数>=i，用下面(citations[n - mid] >= mid) 解决。但是感觉排序再统计的方法更易（注释写的）。
74. 搜索二维矩阵
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int i=0;i<matrix.length*matrix[0].length;i++){
if(matrix[i/matrix[0].length][i%matrix[0].length]==target)return true;
}
return false;
}
}
class Solution {
// public boolean searchMatrix(int[][] matrix, int target) {
// int m = matrix.length;
// int n = matrix[0].length;
// int left = -1;
// int right = m * n;
// while (left + 1 < right) {
// int mid = (left + right) >>> 1;
// int x = matrix[mid / n][mid % n];
// if (x == target) {
// return true;
// }
// if (x < target) {
// left = mid;
// } else {
// right = mid;
// }
// }
// return false;
// }
// }
用一些数学知识来降低时间复杂度，但是for和while循环哪个好，请大家自评吧哈哈哈
162. 寻找峰值
class Solution {
public int findPeakElement(int[] nums) {
int left =0;
int right = nums.length-1;
while (left <right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right =mid;
} else {
left = mid+1;
}
}
return left;
}
}
// class Solution {
// public int findPeakElement(int[] nums) {
// int num=0;
// for(int i=1;i<nums.length;i++){
// if(nums[i]>nums[i-1])num=i;
// }
// return num;
// }
// }
题意可知[0,n−1] 中一定存在峰值那么循环条件就有了，在循环内部计算中间位置 mid。如果 nums[mid] 大于 nums[mid + 1]，则说明峰值元素在 mid 的左侧（包括 mid），将 right 指针移动到 mid。否则，峰值元素在 mid 的右侧，将 left 指针移动到 mid + 1。因为是半开区间查找return 写成right也没问题（解释的话，上面都写过）。
请大家不要忘记一键三连哟~~~
终于写完啦今天比上一次快了半个小时嘿嘿
如有不足请在评论区指出