二分问题

二分段满足条件

• 左部满足,右部不满足
• 右部满足,左部不满足

二分基本问题：

• 求最左: 右部满足,求右部的左(内)边界，即求第一个满足条件元素
• 求最右: 左部满足,求左部的右(内)边界，即求最后一个满足条件元素

左部满足求左边界&右部满足求右边界只需判断左端点和右端点即可

求最右问题构造check函数对左部元素为True

求最左问题构造check函数对右部元素为True

二分划分

选择一个中间点,将整个序列划分为左右两段,然后按照是哪种二分类型,对满足段进行递归划分

单调序列二分问题

通常序列满足偏序性(<=)：

$ i < j \Rightarrow arr[i] \le arr[j] $

此时二分基本问题可以表示为:

Notice: check使用”<=”判断, 非check使用”<”判断

求最右问题构造check函数使用 item <= x

求最左问题构造check函数使用 x <= item

arr[mid] 站在满足的一边，x站在要求的一边

简化为：

”<=”判断满足段, 求最右x居右, 求最左x居左;

”<”判断否定段, 求最右arr[mid]居右, 求最左arr[mid]居左;

根据代码判断是哪一种二分:

”<”或”>=”, mid位置是否定段

”<=”或”>”, mid位置是满足段

递归划分

[0, n - 1] 右闭区间划分法

求最右[mid, rt]需要使用上取整: mid = (lt + rt + 1) >> 1 否则会死循环递归

强行记忆方式

• 求最右, arr[mid] <= x, lt = mid, rt = mid - 1

• 求最左, x <= arr[mid], rt = mid, lt = mid + 1

• 求最右, 左部满足, 左取中, 右左左

• 求最左, 右部满足, 右取中, 左右右
• 最右mid上取整

二分模板

[0, n - 1] OI二分模板(lyd)

• 求最左, 右部满足, 右取中, 左右右, rt = mid, 划分为 [lt, mid] [mid + 1, rt]

lt, rt = 0, n - 1
while lt < rt:
    mid = (lt + rt) >> 1
    if arr[mid] < x: lt = mid + 1
    else: rt = mid

# arr[lt]

• 求最右, 左部满足, 左取中,右左左,lt=mid, 划分为 [mid, rt] [lt, mid - 1], mid 在左边需用”上取整方法”

lt, rt = 0, n - 1

while lt < rt:
    mid = (lt + rt + 1) >> 1
    if x < arr[mid] : rt = mid - 1
    else: lt = mid
# arr[lt]

[first, last) lower_bound & upper_bound

• lower_bound 右满足段求最左

fst, lst = 0, n
while fst < lst:
    mid = (fst + lst) >> 1
    if arr[mid] < x: fst = mid + 1
    else: lst = mid
if fst >= n or arr[fst] != x: print('-1 -1'); continue
else: print(fst, end=' ')

• upper_bound 左满足段求最右

fst, lst = 0, n
while fst < lst:
    mid = (fst + lst) >> 1
    if not (x < arr[mid]): fst = mid + 1
    else: lst = mid
print(fst - 1)

模板例题

789. 数的范围

[0, n - 1] OI二分模板(lyd)

n, q = map(int, input().split())

arr = list(map(int, input().split()))

while q:
    q -= 1
    x = int(input())

    lt, rt = 0, n - 1
    while lt < rt:
        mid = (lt + rt) >> 1
        if arr[mid] < x: lt = mid + 1
        else: rt = mid

    if arr[lt] != x: print('-1 -1');continue
    else: print(lt, end=' ')

    lt, rt = 0, n - 1

    while lt < rt:
        mid = (lt + rt + 1) >> 1
        if x < arr[mid] : rt = mid - 1
        else: lt = mid
    print(lt)

[first, last) lower_bound & upper_bound

n, q = map(int, input().split())

arr = list(map(int, input().split()))

while q:
    q -= 1
    x = int(input())


    fst, lst = 0, n
    while fst < lst:
        mid = (fst + lst) >> 1
        if arr[mid] < x: fst = mid + 1
        else: lst = mid
    if fst >= n or arr[fst] != x: print('-1 -1'); continue
    else: print(fst, end=' ')

    fst, lst = 0, n
    while fst < lst:
        mid = (fst + lst) >> 1
        if not (x < arr[mid]): fst = mid + 1
        else: lst = mid
    print(fst - 1)

两个有序数组求第k个值(0 <= k <= m + n)

double find_kth(int a[], int m, int b[], int n, int k)
{
    if(m > n)    // insure m <= n
        return find_kth(b, n, a, m, k);
    if(m == 0)
        return b[k - 1];
    if(k == 0)
        return min(a[0], b[0]);

    int pa = min(k/2, m), pb = k - pa;
    if(a[pa - 1] < b[pb - 1])
        return find_kth(a + pa, m - pa, b, n, k - pa);
    else if(a[pa - 1] > b[pb - 1])
        return find_kth(a, m, b + pb, n - pb, k - pb);
    else
        return a[pa - 1];
}