1回答

liuyubobobo

2018-04-27

已采纳

我理解你的提问都是基于这个代码：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-02-Floor-and-Ceil-in-Binary-Search/main.cpp

下面的回答中的代码行数，是基于上面链接中的代码来说的：）

问题1：

[2, 3, 4] 在这个数组中，找1的floor，由于数组中最小的元素是2，所以没有比1更小的元素了，此时定义1的floor对应的索引为-1。所以l从-1开始，也就是搜索的解空间在[-1, n-1]之间，-1可能是问题的解。请在看一下7-10行的函数说明：）

问题2：

整个问题的解，在[l, r]这个范围里，如果 l == r，表示已经找到了解，就是l（或者是r），所以有27行的assert(l == r)。此时找到了解，就不应该继续循环了。

问题3：

我们的这个while循环，其实找的是数组arr中，小于target的最大索引。所以有第30行的逻辑，找到这个l之后，再看arr[l+1]是否等于target，等于的话，l + 1是结果，否则的话，l是结果。

因为我们找的是小于target的最大索引，那么arr[mid] >= target的时候，mid都不可能在解的范围里，所以r = mid - 1。

2

1

慕粉3520842

非常感谢！

2018-04-27

共1条回复