淄博云天网站建设推广,河北中保建设集团网站,wordpress登录页改造,南京建设高端网站原教程见labuladong
首先#xff0c;我们建议左右区间全部用闭区间。那么第一个搜索区间#xff1a;left0; rightlen-1;
进入while循环#xff0c;结束条件是rightleft。
然后求mid#xff0c;如果nums[mid]的值比target大#xff0c;说明target在左边#xff0c;…原教程见labuladong
首先我们建议左右区间全部用闭区间。那么第一个搜索区间left0; rightlen-1;
进入while循环结束条件是rightleft。
然后求mid如果nums[mid]的值比target大说明target在左边收缩搜索空间rightmid-1。反之target在右边收缩搜索空间leftmid1。 注意计算mid时不要用mid(leftright)/2这样可能溢出要用midleft(right-left)/2。 以上是经典二分法查找。 但是如果要寻找左右边界呢比如在排序数组中寻找某元素的左右边界。
这时外面的框架不变还是闭区间还是一样的循环结束条件。
但是里面的搜索条件变了。比如搜索左边界的话我们的nums[mid]target这时我们需要往左收缩区间也就是rightmid-1。其他两个条件不变还是在寻找target。
所以他们最终会找不到target最后一次是leftmid1也就是左边界的位置返回left即可。
访问右边界是一样的原理。 这里注意如果整个数组里就不存在targettarget是一个很大的数那么最终leftlen访问溢出了。所以要判断 leftlen。
