【二分】有几种情况？

开门见山，两种情况，分为整数二分和浮点数二分，但一般考的是整数二分，因此列下整数二分的两种写法

当我们在一个排序数组里找某一个元素k时
1、第一种情况：找大于等于k的第一个元素，即绿色区域最左边那个点
这里r = mid，所以mid应该赋值(l+r)>>1而不是(l+r+1)>>1，否则可能无限循环
为什么呢？因为当只有两个数时，如l = 1, r = 2，此时 (l + r + 1) >> 1得到的结果为2，这样r本来就为2，又被赋值为2，无限循环下去

while l < r:
        mid = (l+r) >> 1
        if nums[mid] >= k:
            r = mid
        else:
            l = mid + 1

2、第二种情况：找小于等于k的第一个元素，即红色区域最右边那个点
这里 mid = (l + r + 1) >> 1, 而不是(l+r)>>1，原因同上，可能导致无限循环
比如只有两个数时，l = 1, r = 2, 此时 (l+r)>>1为1，l本来就是1，又被赋值为1，下一次还是1，无限循环
while l < r:
        mid = (l+r+1) >> 1
        if nums[mid] <= k:
            l = mid
        else:
            r = mid - 1

完整代码和测试数据，情况可以自己改来试试
输入：第一排表示数组长度和询问个数，第二排为数组，后面是询问元素，最后输出每个询问元素的起始位置和终止位置（因为可能有多个）
6 3
1 2 2 3 3 4
3
4
5

代码：
n, q = list(map(int, input().split()))
nums = list(map(int, input().split()))
for _ in range(q):
    k = int(input())
    l, r = 0, n-1
    while l < r:
        mid = (l+r) >> 1 # 第一种写法
        if nums[mid] >= k:
            r = mid
        else:
            l = mid + 1
    if nums[l] != k: # 此时l和r一样
        print(-1, -1)
    else: # 说明找到了一个k，那就有右边界，大不了和左边界一样
        print(l, end=" ")
        l, r = 0, n-1
        while l < r:
            mid = (l+r+1) >> 1 # 第二种写法
            if nums[mid] <= k:
                l = mid
            else:
                r = mid - 1
        print(l)

最后求大家米一米！！不扣你们积分的！看帖子积分不够555

不全面吧。即使是针对整数的二分，最常见的也有三大类，变化更是不下十种。
第一类：有序数组的二分。
1.1 没有重复值时找存在的某个值的位置
1.2 有重复的值时找存在的值的最左位置或最右位置
1.3 原数组并不存在要找的值，找最接近的值或者找比它稍微大的最近的值或者比它稍微小的最接近的值
1.4 二维有序数组即矩阵的二分，每行中的整数从左到右是排序的，每行的第一个数大于上一行的最后一个整数 【各种变形都跟一维数组类似，比如不存在找重复最左或接近值等等】
第二类：局部有序但整体不单调数组上的二分。
2.1 有峰数组找最大值或者有谷数组找最小值。比如1, 2, 3, 4, 5, 4, 3, 2里面 找5
2.2 循环数组找值。比如4, 5, 6, 7, 0, 1, 2里面 找6 【各种变形跟有序的类似，比如重复最左或接近值等等】
第三类：隐藏的二分。打眼一看没有明显二分。但是细想一下其实用的是二分来做的题。此类题目的特点是给出了上下的边界数值。
3.1 找平方根或者最接近的平方根的那个整数。经典递归的题目，不完全是二分，确实用到的取中点尝试的步骤。
3.2 比如抄书问题。2个人，抄[2, 3, 4]三本书，求最少抄完花费时间，答案是5 (在答案集合上二分，第一个人抄前两本，第二个抄最后一本，这题动态规划一样可以做)
3.3 比如求最小联通矩形面积（一个由二进制矩阵表示的图，0 表示白色像素点，1 表示黑色像素点。黑色像素点是联通的，即只有一块黑色区域，求最小包含所有黑色的长方形面积）【本质上是对上下左右四个方向分别做四次二分】

我相信还有很多是我一时想不起来甚至根本没遇到的二分的题目。以上列的都是比较常见能在网上找到答案的题目。就不具体写解答了。（主要是懒得找，都是以前刷过的题，比较官方的说法是，篇幅和时间所限云云）

ztztzt8888 发表于 2021-8-3 18:14
不全面吧。即使是针对整数的二分，最常见的也有三大类，变化更是不下十种。
第一类：有序数组的二分。
1. ...

非常感谢关注，回复和贡献！
第一类有序数组都可以用以上模板完成，实际上不一定是对大小排序，其他属性也可以
第二类如2.1也是比较简单的二分，甚至不用套用模板，没有很麻烦的边界问题；而2.2也同2.1，但我还没想到在O(logn)能完成的方法（限于水平
第三类如3.1即前所述浮点数二分，这类问题没有边界问题，只需要限制范围即可，不用套用模板；3.2抄书问题如果是两个人，感觉双指针也可以做，用二分的话感觉需要前缀和数组辅助（emm..我暂时只想到这，当然动规也可以；3.3确实也是可以用二分来完成的题目

其实二分是一种思想，感觉像是tool，前所提供模板是对于一般有序数组进行的二分，基本能解决大部分题，故贴此分享，当然也希望能得到加米~（太缺米了

less_is_more 发表于 2021-8-3 07:06
非常感谢关注，回复和贡献！
第一类有序数组都可以用以上模板完成，实际上不一定是对大小排序，其他属性 ...

2.2 O(logn)的方法就是分情况讨论的标准二分，核心是
（1）包含你选中的mid那个值本身有一侧且仅有一侧是sorted的，那么对于那一侧就可以二分
（2）如果不在有序的一侧，那么那个target必然在另一侧
给你拿java写一下，仅供参考

1. public static int binaryRotatedSearch(int[] arr, int target) {
   
2.    if (arr == null) {
   
3.        return Integer.MIN_VALUE;
   
4.    }
   
5.    int st = 0;
   
6.    int end = arr.length - 1;
   
7.    while (st <= end) {
   
8.        int mid = (st + end) / 2;
   
9.        if (arr[mid] == target) {
   
10.            return mid;
    
11.        }              
    
12.        if (arr[st] <= arr[mid]) { // left part is sorted           
    
13.            if (arr[st] < target && target <= arr[mid]) {
    
14.                end = mid - 1;
    
15.            } else {
    
16.                st = mid + 1;
    
17.            }
    
18.        } else { // right part is sorted
    
19.            if (arr[mid] < target && target <= arr[end]) {
    
20.                st = mid + 1;
    
21.            } else {
    
22.                end = mid - 1;
    
23.            }
    
24.        }
    
25.    }
    
26.    return Integer.MIN_VALUE;
    
27. }

复制代码

分享一个知乎回答：
二分查找有几种写法？它们的区别是什么？ - Jason Li的回答 - 知乎
https://www.zhihu.com/question/36132386/answer/530313852

个人感觉在答案集上面二分是比较难想的，例如wood cut