binary search 的几种写法 到底如何才能运用自如?

2019-07-05 00:32:51 +08:00
 Alpacino
左闭右开有几种写法?如果存在重复值,哪些写法是求上界的,为什么能求上界?哪些是求下界的,为什么能求下届?
闭区间有几种写法?同上
网上找了很多,没有能说的很清楚的。

闭区间和左闭右开:
一个数列分割方法:
[l,mid-1]mid[mid+1,r] while l <= r
[l,mid)mid[mid+1,r) while l < r
这两种分别有什么应用场景?有什么不一样的地方?

LEETCODE 相关题目:
33 Search in Rotated Sorted Array
81 Search in Rotated Sorted Array II
153 Find Minimum in Rotated Sorted Array
154 Find Minimum in Rotated Sorted Array II

这些题目中,到底怎么决定是拿 nums[mid]和左边 nums[left]的值比,还是和右边 nums[right]的值比?

154 的讨论区中,大家都是拿 nums[mid]和 nums[right]比较。是为什么?我尝试用 nums[mid]和 nums[left]比较没有办法处理已经 sorted 的 array。

再请问因为 mid 是向下取整的,所以和左边比较的时候,必须 nums[low] <= nums[mid]?
584 次点击
所在节点    问与答
0 条回复

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/580163

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX