作者：ChiuChiuLIN | 来源：互联网 | 2023-10-10 21:31
文章目录 前言 [x,y] 左闭右闭写法&＃xff1a; [x,y) 左闭右开写法&＃xff1a; 练手题目 总结
前言 之前写二分法的时候没有章法&＃xff0c;乱拳打死老师傅的感觉&＃xff0c;我估计大家也是经常在下面几种情况出错&＃xff1a;left和right之后&＃xff0c;进入while循环&＃xff0c;到底是while(left还是while(left<&＃61;right) 。left&＃61;mid还是left&＃61;mid&＃43;1
然后跟卡子哥系统的学了学&＃xff0c;总结一下&＃xff0c;这里需要的区分是先看定义的区间是[x,y]还是[x,y)
[x,y] 左闭右闭写法&＃xff1a; 1.先定义left和rightleft &＃61; 0right &＃61; 目标数组长度-1
2.进入while循环&＃xff0c;确定while里面是<还是<&＃61;<&＃61;。while(left<&＃61;right)mid &＃61; (left&＃43;right)/2
3.然后判断目标值和mid的大小关系&＃xff0c;更新左右区间。if (目标值right &＃61; mid -1mid-1而不是mid,因为此处写的是左闭右闭区间&＃xff0c;可以想象&＃xff0c;在检查的时候左右边界都包含其中&＃xff0c;也就是mid无论在那个位置&＃xff0c;都是已经检查过的值了。
4.最后就是其他两种的情况&＃xff1a;if (目标值>mid) # 更新右边区间的左边界left &＃61; mid &＃43;1else return midmid&＃43;1 而不是mid
[x,y) 左闭右开写法&＃xff1a; 1.先定义left和rightleft &＃61; 0right &＃61; 目标数组长度
2.然后就是while循环里的符号&＃xff0c;<&＃61;因为尽可能检查多的元素且<&＃61;在左闭右闭区间内合法&＃xff0c;但在左闭右开区间内不合法&＃xff0c;所以使用<while(leftmid &＃61; (left&＃43;right)/2
3.然后判断目标值和mid的大小关系&＃xff0c;更新左右区间。if (目标值right &＃61; midelif (目标值>mid) # 更新右区间的左边界left &＃61; mid &＃43;1else return midmid而不是mid-1,因为此处写的是左闭右开区间&＃xff0c;可以想象&＃xff0c;之前写左闭右闭的时候&＃xff0c;两个边界都包含其中&＃xff0c;此时左边界包含其中&＃xff0c;有边界不包含其中&＃xff0c;所以在更新有边界的时候是mid而不是mid-1&＃xff0c;同理&＃xff0c;在更新左边界的时候&＃xff0c;是left &＃61; mid &＃43;1
练手题目 leetcde 704 二分查找
总结 其实还有一个疑问就是这两种区间怎么选择的问题&＃xff0c;我还没搞清楚明确的思路&＃xff0c;但是放到题里直接用第一个左闭右闭区间就行&＃xff0c;然后就是还有左开右闭区间&＃xff0c;不过基本不怎么用&＃xff0c;道理其实也和上面一样就不多说了&＃xff0c;后面去刷题的时候有什么发现再补充吧。
京公网安备 11010802041100号