二分法查找边界

一串数据,分为左右两个部分,一部分符合条件,一部分不符合条件。现在需要通过二分法找到边界。

比如这样一串数据,符合条件情形如下:

[Y, Y, Y, Y, N, N]

查找逻辑需要符合几个条件:

  1. 有退出循环条件。
  2. 每次循环,左指针或者右指针发生变化,否则会死循环。
data: 数据
l: 左指针
r: 右指针
m: 中间指针
for l <= r {
  m = (l + r) / 2
  if data[m] == Y {
    l = m + 1
  } else {
    r = m - 1
  }
}

这时 data[l] 是边界(N)。