我希望每个人都过得很好。
我知道有很多问题的标题与我的问题非常相似,但我对起始值和结束值有疑问:-
>
如果我使用停止条件作为启动
而(l
if(arr[mid]==k)
return mid;
else if(k>arr[mid])
l=mid+1;
else
r=mid-1;
}
从开始=-4到结束=-4,结果是错误的。
我已经阅读了其他问题并了解到更改停止条件会更改开始和结束的范围(包括/排除),但是,
为什么二叉搜索在 start=0/-1/-2/-3 到 end=n/n 1/n 2/n 3 时有效?我的意思是除了开始 mid=(n-2 2)/2
感谢您花费宝贵的时间来解答我的疑问。
我希望我写得清楚。
如果我使用停止条件作为开始
这不是真的。start
和 end
必须精确地从数组的第一个和最后一个索引开始,否则会出现您提供的算法失败的情况。因此,假设从零开始的数组索引,start = 0,end = n - 1
是此算法唯一正确的初始化。
以下是一些替代方案的反例:
>
start=0,end=n
:如果k
是一个大于arr
中最大值的值,那么最终mid
将等于n
rr[mid]将会是一个无效引用。根据语言的不同,这可能会触发异常。
start=-1,end=n-1
:如果k
是一个小于arr
中最小值的值,那么最终mid
将等于-1,rr[mid]
将会是一个无效的引用。
< code>start = -2,end = n - 2如果< code>k == arr[0]和< code>n == 3,将找不到元素,因为< code>mid将获得值-1。
开始 = -2,结束 = n 2
。如果 k == arr[0]
和 n == 3
,则找不到该元素,因为 mid
将获得值 1,而在下一次迭代中它将为 -1,因此永远跳过索引 0。
…等等