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

来源：5-1 二分查找法（Binary Search）

水瓶座妙妙

2017-03-06

老师的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时，程序运行会发生什么？

写回答

2回答

liuyubobobo

2017-03-06

assert 就是保证断言的内容为真哦。这里 assert( l == r ) 和你分析的一样，就是确保上面的 while 循环中，最终退出循环的时候是 l==r。如果 l==r 则没有问题，继续进行下面的代码，否则在debug时会报错哦。
l 初始化值为-1。若arr[l] > target，在二分搜索的过程中，最终r也会成为-1，和 l 相等，退出while循环。最后的 return l; 使得整个算法返回了-1 ：）