binary search

• binary search
  • sort.SearchInts使用技巧
  • sort.Search的使用技巧
  • 套路
    • 最大化最小值/最小化最大值
      • 例题
  • 参考
    • 蓝红二分

sort.SearchInts使用技巧

lowerBound := sort.SearchInts
upperBound := func(a []int, x int) int { return sort.SearchInts(a, x+1) }
upperBound = func(a []int, x int) int { return sort.Search(len(a), func(i int) bool { return a[i] > x }) }

等于 x 的下标范围：[lowerBound(x), upperBound(x)) lowerBound-1 为 <x 的最大值的下标（-1 表示不存在），存在多个最大值时下标取最大的 upperBound-1 为 <=x 的最大值的下标（-1 表示不存在），存在多个最大值时下标取最大的

sort.Search的使用技巧

// go.Search注释
// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true
// 使用二分查找,返回最小的i使f(i)为true,没有找到为true的i,将返回n

// Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.
// 未找到不返回-1(和strings.Index行为不同)

sort.Search(n, f) 需要满足当 x 从小到大时，f(x) 先 false 后 true 若 f(x) 是先 true 后 false，且目标是找到最大的使 f(x) 为 true 的 x 这种情况可以考虑二分 !f(x)，则二分结果是最小的使 f(x) 为 false 的 x，将其 -1 就得到了最大的使 f(x) 为 true 的 x 由于要对结果 -1，sort.Search 传入的上界需要 +1 更加简单的写法是，在 f(x) 内部将 x++，这样就不需要对上界和结果调整 ±1 了

下面以二分求 int(sqrt(90)) 为例来说明这一技巧 这相当于求最大的满足 xx<=90 的 x 于是定义 f(x) 返回 xx<=90， 注意这是一个先 true 后 false 的 f(x) 我们可以改为判断 f(x+1)，即用 f(x+1) 的返回结果代替 f(x) 的返回结果 同时， 将 f(x) 改为先 false 后 true，即返回 x*x>90 这样二分的结果就恰好停在最大的满足原 f(x) 为 true 的 x 上

sort.Search(10, func(x int) bool {
  x++
  return x*x > 90
})

套路

最大化最小值/最小化最大值

看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。 为什么？一般来说，二分的值越大，越能/不能满足要求；二分的值越小，越不能/能满足要求，有单调性，可以二分。

例题

• Leetcode 2560. 打家劫舍 IV 题解
• Leetcode 2439. 最小化数组中的最大值
• Leetcode 2513. 最小化两个数组中的最大值
• Leetcode 2517. 礼盒的最大甜蜜度
• Leetcode 2528. 最大化城市的最小供电站数目

参考

• codeforces-go
• 二分模板,二分的本质是什么 二分法（dichotomy）指的是将一个整体事物分割成两部分。也即是说，这两部分必须是互补事件，即所有事物必须属于双方中的一方，且互斥，即没有事物可以同时属于双方。
• 蓝红二分法
• 二分模板

蓝红二分

主体思路：l 指针掌管左边蓝色区域,r 指针掌管右边红色区域，两者互不冲突 通过不断向目标元素靠近扩大掌管区域，直到两者掌管区域接壤，即 l + 1 == r时终止。

开始时，l 指针和 r 指针取在搜索区间界外，l = 首个元素下标 - 1，r = 末尾元素下标，此时所有元素均未着色； 循环条件始终为 l + 1 ≠ r,当 l + 1 == r时跳出循环，此时蓝红区域划分完成，所有元素均已着色； mid指针取值始终为 mid = floor (l + r) / 2 l 指针和 r 指针变化的时候直接变为 mid指针，即对 mid指针所指向元素进行染色，无需 +1或者 -1； 本模板唯一变化的地方是判断目标元素最终落在左边蓝色区域还是右边红色区域。

l,r:=-1,len(v)-1
for l+1<r{
  m:=int(unit(l+r)>>1)
  if isBlue(m)
    l = m
  else
    r = m
}

// 或
l,r:=-1,len(v)-1
for l+1<r{
  m:=int(unit(l+r)>>1)
  if isRed(m)
    r = m
  else
    l = m
}

作者：sui-xin-yuan 链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-aray/solution/lan-hong-hua-fen-fa-dan-mo-ban-miao-sha-e7r40/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

＜ 、≤ 、≥ 、＞ 目标元素 target 对应的蓝红区域划分