寻找数组中满足条件的某个数

问题

有一个数组

下标 i 之后连续的一些数满足/不满足某个条件

即 […, i, true, true, true, true, false, false, …]

check(index) 检查下标为 index 的数是否满足条件

i 是下标, true 和 false 表示对应的数是否满足条件

目标

1. 找到最后一个满足条件的数, 返回下标, 即最后一个连续 true 的下标
2. 找到第一个不满足条件的数, 返回下标, 即第一个 false 的下标

解法

1. 正向搜索

[..., i, true, true, true, true, false, false, ...]

// 最后一个满足条件的数, 最后一个 true
int j = i + 1;
while(j + 1 < n && check(j + 1)) j++;

// 第一个不满足条件的数, 第一个 false
int j = i + 1;
while(j < n && check(j)) j++;

2. 反向搜索

[..., false, false, true, true, true, true, i, ...]

// 最后一个满足条件的数, 最后一个 true
int j = i - 1;
while(j - 1 >= 0 && check(j - 1)) j--;

// 第一个不满足条件的数, 第一个 false
int j = i - 1;
while(j >= 0 && check(j)) j--;