二分查找算法详解（查找左右端点二分）_二分查找左端点

一.特点

最恶心，细节最多，最容易写出死循环的算法。（掌握后就变成最简单的算法）

二.学习中的侧重点

1.算法原理

用二分查找算法，并不是一定要有序，只要发现数组有一定规律，就可以使用。

2.模板

不要死记硬背->理解之后再记忆
有三个模板：
1朴素的二分模板（简单，但有局限）
练习题：二分查找

2查找左边界的二分模板（万能，细节多）
3查找右 边界的二分模板 （万能，细节多）
2和3的练习题： 在排序数组中查找元素的第一个和最后一个位置

二、朴素二分

1.样例题目（以小见大）

先别急的做，可以点开看题目，再看下面讲解再做！
题目链接：二分查找
题目：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

二分查找题解：

---

首先我看如何用暴力解决题目？
就是简单从左往右遍历，一次可以排除一个元素，直到找到或者遍历结束。

---

因为数组有序，我们可以使用二段性。
先在数组中随便找一个数A，再与目标数比较
1.如果等于就表示数A就是我们找的目标数
2.如果数A小于目标数，就表示目标数在数A的右边。
3.如果数A大于目标数，就表示目标=数在数A的左边。
这一次比较就排除了包括数A和它一边的数，效率比暴力大大提升。

重复上面的操作直到找到，或者没有选取地方。

---

但如何选数A？
无脑选最中间的数，别问我为什么，跟数学期望有关。

---

t是目标数 x是数组下标为mid的值

1.x<t -> left = mid+1 -> [left,right]
2.x>t -> right = mid-1-> [left,right]
3.x==t -> 返回结果

细节问题：
1,循环结束的条件
提问：在[left,right]里我们都没有判断，当left=right时，我们依旧要去判断由此可以推断出：
结束循环的条件是：left>right

2.为什么是正确的？
二分的解法，是在暴力解法优化过来的。

3.时间复杂度
log2n

解题代码：

class Solution {
    public int search(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)return mid;
            else if(nums[mid]<target)left = mid+1;
            else if (nums[mid]>target)right = mid-1;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.朴素二分模板

while(left<=right)//一定要写 <=
{
	//求mid写法是防溢出，当数据量是偶数时指向靠左
	//还有一种写法是mid = left+(right-left+1)/2;当数据量为偶数时，指向靠右
	//两种写法在数据量为奇数时没有区别
	int mid = left+(right-left)/2;
	if(''''')
	left = mid+1;
	else if(''''')
	right = mid-1;
	else 
	return ''''';
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三、左端点和右端点二分

1.样例题目

题目链接： 在排序数组中查找元素的第一个和最后一个位置
题目：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

题解：

---

首先我看暴力解法：

从左往右遍历遇到第一个就是元素第一个赋给元素第一和最后一个返回值，接的遍历下去，遇到新的再更新返回最后的值。

---

查找区间的左端点：
利用二段性：
可以把数组分成左边小于t,右边大于等于t.

1. x<t 就表示 mid 和 left 之间没有要找的左端点，left = mid+1，
2. x>=t 就表示 mid 到 right （不包括mid）不是要找的左端点 right= mid;

处理细节：
1.循环条件
left<=right --错
left<right --对

为什么选 left < right
分情况讨论：
①有结果:
left在小于t之间移动，一直想跳出小于t的区间
right在大于等于t之间移动，不会超过左端点
当left==right就是我们要的结果，无需判断

②全大于t
right一直向左移动直到与left相遇，因为没有结果，只需判断left的值是不是左端点的值

为什么可以一直向左移动（因为mid一直选靠左的）当还是剩两个mid =0 因为大于t right = mid从而相遇

③全小于t
left一直向右移动，直到与right相遇，当left==rgiht就是结果，再判断结果是否为找的左端点。

---

如果判断，就会死循环
在上面第一种情况下：
当left == right
arr[mid] == t
就是执行 right= mid
就会一直left==right 反复判断进而死循环，无法跳出。

---

综上：
1.left==right,就是最终结果，无需判断
2.如果判断，就会死循环

2.求中点的方式
①left+(right-left)/2 （求的是靠左）
②left+(right-left+1)/2（求的是靠右）

1. x<t 就表示 mid 和 left 之间没有要找的左端点，left = mid+1，
2. x>=t 就表示 mid 到 right （不包括mid）不是要找的左端点 right= mid;

当只剩两个，如果求mid选②
如果是1.情况，可以跳出循环
如果是2.情况，就会一直mid = right, right =mid 进如死循环

当只剩两个，如果求mid选②
如果是1.情况，left = mid +1就会和right重合跳出循环
如果是2.情况，right = mid 同样和left重合跳出循环

所以要用①求中点

查找区间右端点
利用二段性：
可以把数组分成左边小于等于t,右边大于t.

1. x<=t ->left=mid
2. x>t -> right =mid -1 理由同上

处理细节：
1.循环条件：
left<right
理由同上

2.求中点的方式
mid = left+(right-left+1)/2 (求中点靠右)

理由：和上面一样如果用求中点靠左的就会进入死循环

解题代码：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1,-1};
        int left =  0 ;
        int right = nums.length-1;
        if(right<0) return ret;  //可能数组为空
        //找左端点 根据二段性 分为小于target,和大于等于t 1.x<t 2.x>=t
        while(left<right)
        {
            int mid = left+(right-left)/2;  //取靠左
            if(nums[mid]<target) left = mid+1;
            else right = mid;
        }
        if(nums[left]!=target) return ret;
        ret[0] = left;
        left = 0;
        right = nums.length-1;
        //找右端点 根据二段性 分为小于等于t,和大于t 1.x<=t 2.x>t
        while(left<right)
        {
            int mid = left+(right-left+1)/2; //取靠右
            if(nums[mid]<=target) left = mid;
            else right = mid-1;
        }
        ret[1] = right;
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.总结二分模板

查找区间左端点的模板

while(left<right)
{
int mid = left +(right -left)/2;
if(.....) left = mid +1;
else right = mid;
}
1
2
3
4
5
6

查找区间右端点的模板

while(left<right)
{
int mid = left +(right -left+1)/2;
if(.....) left = mid;
else right = mid -1;
}
1
2
3
4
5
6

if（…） …里的要根据题目二段性得出。

三、其他二分练习题

练习题1
练习题2
练习题3
练习题4
练习题5
练习题6