二分查找法floor和ceil的边界问题

Question

我看了一下老师的代码。没咋理解注释的那些点。能麻烦老师详细讲解下floor的实现细节么

Answer 1

liuyubobobo 2020-09-17 15:36:07

具体是哪一个点没有理解？

• 提问者 慕九州5549167 #1

  整个循环的过程。。。mid的取值问题，为啥会死循环。还有就是arr[mid] == target的处理。以及最后那个 l + 1的判断。。。不太理解整体的思路

• liuyubobobo 回复 提问者 慕九州5549167 #2

  首先，你将 r - l + 1 改成 r - l，用一个数据跑一遍代码，应该就能碰到死循环。使用一个八个数据的用例试试看？遇到死循环以后，仔细跟踪以下代码，看一看问题发生在哪里。（在 l 和 r 相邻的时候，会产生这种情况。核心在于对 l 的更新是 mid，可能导致 l, r 不变。所以，产生了死循环。使用上取整，保证了早 l, r 相邻的时候一定变化）
  
  后面的判断，是因为上面的二分搜索得到的是比 target 小的最大索引。但这不是 floor 的定义。比如对于 0 1 1 1 1 2。1 的 floor 是索引 1，指向第一个 1。但是比 target 小的最大索引是 0，指向 0。所以，要验证一下比 target 小的最大索引 l 是不是等于 target，如果等于, l + 1 才是 floor 的结果，否则 l 是 floor 的结果。
  
  继续加油！：）

• 提问者 慕九州5549167 回复 liuyubobobo #3

  还有就是循环结束的条件怎么判断呢，我看有的是l<r，有的是l<=r

点开查看后面6条评论