二分法我之前在CSDN上写过二分法及其注意事项。现在来优化一下代码。在CSDN上的文章中有一个查找数在数组中范围的代码,那里是根据算法笔记上写的。但在实践过程中发现,如果要求的数位于数组的末尾,那么将无法正确返回数的区间。
原来的代码:
1 | #include "stdio.h" |
这串代码返回的是所要查找的数的左闭右开区间,但是如果数在末尾,返回的均是闭区间。因为right是从最右边开始扫的。
修改后的代码(yxz)
1 | #include "iostream" |
算法基础课上学的,返回的两边都是闭区间,这样就很好的避免了上述特殊情况的出现。
寻找右闭区间↓
1 | while(l<r) |
这里面求mid时有个+1 的操作,这个是为了mid能够向前进,而不至于陷入死循环。例如:l=4,r=5,那么int型的mid=4而如果a[mid]恰好等于x,那么就始终执行l=mid。那为什么不写成mid=l+r>>1+1呢?这是因为我们不希望mid前进的过多,以至于影响了其他可以执行的数。
题目讲解链接>>
本文作者: jiangyuhao
本文链接: http://example.com/2022/01/30/%E4%BA%8C%E5%88%86/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!