algorithm - 二进制搜索以查找布尔数组中的最高真实索引

Question

我有一个布尔数组，[true, false, false, false, true]我需要找到最高索引（0到1000之间）true，我认为二进制搜索是最好的方法，但我不知道如何调整算法来完成我需要的.

标签： algorithmbinary-search

Answer 1

二进制搜索可以应用于有序（非递减/非递增）函数。
您的布尔数组似乎没有这样的顺序。
像这样想，如果你在当前元素上说mid，如果arr[mid] == false，你会跳到哪里？右半边还是左半边？要决定从哪里跳转，您需要对布尔数组进行一些排序。

现在谈到你的问题，你可以有两种方法：

1. 只需从结束索引反向循环并在遇到的第一个布尔值处中断。
2. 如果您可以将布尔数组存储为位掩码表示，那么您可以及时找到最右边的设置位log(n)。