Hot100之二分查找
二分基本模板
找到最右边的第一个答案
我们这样子得到的结果其实和我们的mid=（left+right）/2是一样的
mid=left+(right-left)/2;
int left=0;
int right=0;
while(left<=right)
{
if(nums[mid]<=target)
left=mid+1 // 遇到7或者小于7一直往右
else if(nums[mid])>target
right=mid-1 //遇到最右边的7的时候挺下来
}
//这个是【1，3，7，7，7】中找到最右边的7找到最左边的第一个答案
这个是【1，3，7，7，7】中找到最左边的7
int left=0;
int right=0;
while(left<=right)
{
if(nums[mid]<target)
left=mid+1 //遇到左边第一个7就停下来
else if(nums[mid]<=target)
right=mid //大于7或者等于7的时候，继续往左，直到left=right停止
}
其实主要的逻辑还是，我们的if else里面，，主要是我们的left在变还是我们的right在变
因为这会觉得我们得到的答案的下标是left还是right
主要在于=target的时候，我们是left移动还是我们的right移动
然后我们的答案是return我们的left还是right也是有讲究的
特殊情况
还有一种情况就是【1，1，1，1，2，2，2，3，3，3，3】
我们要是不处理left和right的逻辑的话
我们假设要找到3
我们可能想找的是第一个3，要是不处理逻辑的话，我们找到的就是我们的最后一个3
二分答案（答案具有单调性）
其实就是我们的答案有单调性
我们找到我们的答案的判断条件
找到我们的left和right的范围
然后
我们只要不断缩小我们的答案的区间来尝试，就可以得到正确的答案了
其实就是确定我们的答案的范围，然后不断地搜索答案
最具体的例题（分巧克力）
我们知道判断条件后，知道答案肯定在某个数之间，我们直接二分答案，暴力搜索出来
35搜索插入位置
题目
思路解析
为什么return left呢？
因为我们有一种情况是【4，5，6，7】我们是8，在数组之外的最后面
还有一种情况是【1，2，3，4】我们是0，在数组最前面
你看我的代码逻辑，此时就是返回left
为什么返回mid？
if(nums[mid]==target){
return mid;
}因为我们的题目要求我们和数组数字相等的时候，我们就插入这个位置
【1，3，5，6】我们是5
插入的位置是5，也就是index2，此时我们的mid=5也就是和该下标的元素相等
代码
class Solution {
public int searchInsert(int[] nums, int target) {
int left=0;
int right=nums.length-1;
int mid=(left+right)/2;
while(left<=right)
{
mid=(left+right)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
left=mid+1;
}
else if(nums[mid]>target){
right=mid-1;
}
}
//这个是最重要的 return left;
return left;
}
}
74搜索二维数组
题目
递增的二维数组
思路解析
因为是递增的二维数组
所以我们可以从每一行的最后一个开始往前找，因为每一行的最后一个是该行的最大元素
如果target比这行的最后的数大，说明不在这行，我们跳转到下一行继续找
如果target比这行的最后的数小，说明在这行，我们从后往前找，找到第一个元素都没找到，就说明该元素不存在了
代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length;
int n=matrix[0].length;
for(int i=0;i<m;i++)
for(int j=n-1;j>=0;j--)
{
if(matrix[i][j]==target)
return true;
//如果我们该行最大的数字都小于target,那就说明不在这行,跳到下一行
if(matrix[i][n-1]<target)
break;
//我们确定这个数字在这行的范围内,但是我们找到第一列最小那个发现找不到,那就说明不可能存在了
if(matrix[i][0]>target)
return false;
}
return false;
}
}
34在排序数组中查找元素的第一个和最后一个位置
题目
思路解析
我们通过二分，也就是通过相等的时候让right---的逻辑，来找到在最左边的第一个目标元素
如果第一个目标元素都找不到，那就说明这个元素不存在了
我们直接return{-1,-1}
我们找到第一个元素之后我们该怎么找第二个元素？
我们换一个思路，因为我们此时的二分逻辑是找目标元素的最左边的第一个元素
那我们让我们要找的目标target+1，是不是就可以找到比目标元素大的第一个元素的位置，然后我们-1，就能找到最右边的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};我们会有找不到的情况，例如我们找出界了，在第一个的最前面或最后一个的后面
说明我们找不到
针对这种不存在元素的时候我们有个初始判断
start==nums.length说明我们在最右边出界了
nums[start]!=target说明我们要找的元素在左边出界了或者中间找不到元素所以我们要判断结果是否正确
if(start==nums.length||nums[start]!=target)
return new int[]{-1,-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};
}
private int lowerBound(int [] nums,int target)
{
int left=0;
int right=nums.length-1;
while(left<=right)
{
int mid=left+(right-left)/2;
if(nums[mid]<target)
{
left=mid+1;
}
else{
right=mid-1;
}
}
return left;
}
}红蓝染色法的思维模式
红蓝染色法这里看了很久，尤其是162题，感觉很不好理解，下面是自己的看法。
1、红蓝染色法定义好红色和蓝色的规则，移动left还是移动right，取决于哪边的区间还没有确定，如果可以确定mid右侧都是蓝色，就移动right，可以确定mid左侧都是红色，就移动left。
这点跟我自己学二分查找的时候思路不太一样，比如我在做寻找数组中target的索引的时候，我会想着target在mid的右侧还是左侧，然后再去这个区间里找，比如mid<target了，那我就应该在右边找，所以让left＝mid。
如果用红蓝染色法的思维，应该是mid<target了，那就可以确定左边都是红色，但是右边还不能确定，所以移动left。这个思路应该说既相似又相反，需要多去理解
2、162这个题，定义峰顶或者峰顶的右侧为蓝色，假如mid>mid+1，那么mid要么是峰顶，要么在峰顶的右侧，这个时候，mid的右边也一定在峰顶的右侧，所以mid之后的都可以染成蓝色。这个地方我纠结了很久，才终于明白，mid都在峰顶的右侧了，mid后面的部分当然更在峰顶的右侧了。
3、红蓝染色法，染色就相当于有一个falg=【0】 * n的标记，将整个数组都打上了一个标签，往往答案就在红蓝染色的交界。从这几道例题来看，往往定义蓝色是包含着答案的解，答案应该是蓝色区间的最左侧，这是最后判断取L还是取R或者L-1等等的本质，也就是循环不变量
162寻找峰值（红蓝染色法示例题162）
题目
思路解析
首先，我们相邻的数不相等，所以根据这个相邻的数不相等的逻辑
我们知道3个数字之间肯定会出现一个峰值，而我们的mid肯定是在两个数之间的，所以要不mid是峰值要不就在mid的左右，所以我们根据红蓝染色法指针不断收缩，肯定能找到一个峰值
如果我们的nums【mid】<nums【mid+1】
所以mid和mid左边染成红色
如果是nums【mid】>nums【mid+1】
说明要不这个数是峰值，要不这个数在峰值的右边
所以我们把mid和mid右边染成蓝色
代码
class Solution {
public int findMin(int[] nums) {
int left=0;
int right=nums.length-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<nums[nums.length-1])
//因为我们的nums[mid]也有可能是我们的最小值，所以我们不能right=我们的mid+1，
//不然就把我们的最小值排除了
right=mid;
else
left=mid+1;
}
return nums[left];
}
}153寻转旋转排序数组中的最小值（红蓝染色法示例题153）
题目
思路解析
我们用二分的话
我们就要判断我们的nums【mid】是在我们的最小值的左侧还是最小值的右侧
我们可以和最后一个数比大小，由于最小值一定在数组中，那么最后一个要么是最小值，要么在最小值右侧
所以n-1这个位置肯定被染成蓝色
所以我们可以在0----n-2这个位置二分
如果nums【mid】小于最后一个数
那么有两种情况
一 在一段递增数组中
如 3 5 6 7 8 9
二 在两段递增数组的第二段
3 4 5 6 1 2
因为nums【mid】小于最后一个数
无论是哪种情况我们的nums【mid】要么是最小值
要么在最小值右侧
如果小于最后一个数，我们就染成蓝色，其他就染红色
我们考虑数组中的最后一个元素 xxx：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 xxx；而在最小值左侧的元素，它们的值一定都严格大于 xxx。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。
这是我的做法
其实我们的逻辑就是
如果我们的nums【mid】小于我们的最后一个数nums【n-1】
那么我们的最小值肯定在nums【n-1】的左边
所以我们染成蓝色，但是我们的nums【mid】也有可能是最小值
所以我们缩小区间的时候，不可以right=mid-1
而是right=mid
然后我们的while应该是（left<right）而不是（left<=right）
因为按照我们的逻辑，left和right相遇的时候，我们此时的值就是我们的最小值
代码
class Solution {
public int findMin(int[] nums) {
int left=0;
int right=nums.length-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<nums[nums.length-1])
//因为我们的nums[mid]也有可能是我们的最小值，所以我们不能right=我们的mid+1，
//不然就把我们的最小值排除了
right=mid;
else
left=mid+1;
}
return nums[left];
}
}33搜索旋转排序数组
题目
思路解析
我们的升序数组被打乱了，我们该怎么根据时间复杂读为O（logn）的二分算法解决这个问题？
我们进行两次二分
一次用题目153的红蓝染色法找出最小值的位置
然后我们通过和最后一个值来比较+我们的最小值，找出我们的要找的值究竟在哪一个区间
然后在这个区间再二分一次
代码
class Solution {
public int search(int[] nums, int target) {
if(nums[nums.length-1]==target)
return nums.length-1;
int left=0;
int right=nums.length-1;
int mid=0;
while(left<right)
{
mid=left+(right-left)/2;
if(nums[mid]<nums[nums.length-1])
//因为我们的nums[mid]也有可能是我们的最小值，所以我们不能right=我们的mid+1，
//不然就把我们的最小值排除了
right=mid;
else
left=mid+1;
}
//上面我们找出了，left是我们的最小值所在的位置
if(left==0)
right=nums.length-1;
else if(left!=0&&nums[nums.length-1]<target)
{
right=left-1;
left=0;
}
else if(left!=0&&nums[nums.length-1]>target)
{
right=nums.length-1;
}
while(left<=right)
{
mid=left+(right-left)/2;
if(nums[mid]<target)
{
left=mid+1;
}
else{
right=mid-1;
}
}
if(left>nums.length-1||nums[left]!=target)
return -1;
return left;
}
}