一串数据,分为左右两个部分,一部分符合条件,一部分不符合条件。现在需要通过二分法找到边界。
比如这样一串数据,符合条件情形如下:
[Y, Y, Y, Y, N, N]
查找逻辑需要符合几个条件:
- 有退出循环条件。
- 每次循环,左指针或者右指针发生变化,否则会死循环。
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)。