一串数据,分为左右两个部分,一部分符合条件,一部分不符合条件。现在需要通过二分法找到边界。
比如这样一串数据,符合条件情形如下:
[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)。