关于老师的Github中floor函数的疑问

Question

老师的Github的代码的关键部分如下：

// 寻找比target小的最大索引    
int l = -1, r = n-1;    
while( l < r ){    
    // 使用向上取整避免死循环    
    int mid = l + (r-l+1)/2;    
    if( arr[mid] >= target )    
        r = mid - 1;    
    else    
        l = mid;    
}    
assert( l == r );

我有两处疑问：

第一个是，我尝试理解了下，根据while循环体内的代码逻辑，while( l < r )循环的退出条件必定是 l == r，但后面紧接着出现 assert( l == r )，此时assert括号内恒为true，程序不是必然会退出吗？后面的代码不就无法执行了？

第二个是，注释的最后一行是：“如果这个target比整个数组的最小元素值还要小, 则不存在这个target的floor值, 返回-1”，可代码中并未出现 return -1;啊，如果真出现arr[l...r]中不存在floor值，即arr[l]>target时，程序运行会发生什么？

Answer 1

liuyubobobo 2017-03-06 23:07:13

1. assert 就是保证断言的内容为真哦。这里 assert( l == r ) 和你分析的一样，就是确保上面的 while 循环中，最终退出循环的时候是 l==r。如果 l==r 则没有问题，继续进行下面的代码，否则在debug时会报错哦。

   
   

2. l 初始化值为-1。若arr[l] > target，在二分搜索的过程中，最终r也会成为-1，和 l 相等，退出while循环。最后的 return l; 使得整个算法返回了-1 ：）
   

• 提问者 水瓶座妙妙 #1

  对啊！脑子糊涂了，这么基础的问题，哈哈，有劳老师解答了。

Answer 2

qq_老虎_daniu 2017-06-01 15:14:52

这个floor函数 和 ceil函数的实现在哪呢, 我怎么没找到啊

• liuyubobobo #1

  请参见这个课程的官方git代码仓：https://github.com/liuyubobobo/Play-with-Algorithms