二分算法（二）
我们都知道二分查找的大致思路，就是定义一个左指针和一个右指针，去这两个指针的中间值，判断是否和目标值一样，如果一样就返回当前下标；如果不等于，就判断中间值与目标值的大小，如果中间值小于目标值，那么左指针就走到中间值下标+1 的位置；如果中间值大于目标值，那么右指针就走到中间值下标-1 的位置，以此类推。
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left<=right){
int index = left + (right-left)/2; //
int val = nums[index];
if(val == target){
return index;
}
else if(val<target){
left = index+1;
}
else{
right = index-1;
}
}
return -1;
}
}这里有两个问题需要思考
1、while 当中是<=为什么不是<?
小于等于表示搜索区间两侧都能取到，比如[left, right]，如果只是小于的话，搜索区间就表示[left, right)， 右边就取不到了。
2、为什么是 left = index+1?
因为我们使用的是两边毕区间的搜索区间，所有当发现 index 的位置不是我们的目标值的时候，就会从 index-1 或者 index+1 的范围再来计算
20240409 更新
今天早上早看了灵神的关于二分查找的视频之后， 感觉豁然开朗了，很推荐大家都看一下，会有不一样的收获，视频地址：二分查找 红蓝染色法
这里贴一下我做过的用到二分查找的题目
这里也贴一下灵神关于二分查找总结的一份力扣的题单，对学习二分一定有帮助
二分算法（二分答案/最小化最大值/最大化最小值/第 K 小）
34. 在排序数组中查找元素的第一个和最后一个位置
>=, <= 都可以转化用 lowerBound 来转化
比如>=x 直接用， <=x 可以转化成>= x+1, 最后取下标减一。
class Solution {
public int[] searchRange(int[] nums, int target) {
// 二分
int start = lowerBound(nums, target);
if(start == nums.length || nums[start] != target){
return new int[]{-1, -1};
}
int end = lowerBound(nums, target+1) -1;
return new int[]{start, end};
}
public int lowerBound(int[] nums, int target){
int left = -1;
int right = nums.length;
while(left + 1 < right){
int mid = left + (right-left)/2;
if(nums[mid] < target){
left = mid;
}
else{
right = mid;
}
}
return right;
}
}