Java资源分享网 - 专业的Java学习网站 学Java,上Java资源分享网
labuladong的算法秘籍V2.0(力扣版) PDF 下载
发布于:2024-03-17 16:10:30
(假如点击没反应,多刷新两次就OK!)

labuladong的算法秘籍V2.0(力扣版) PDF 下载 图1

 

 

 

资料内容:

 

3、为什么 left = mid + 1right = mid ?和之前的算法不⼀样?

答:这个很好解释,因为我们的「搜索区间」是 [left, right) 左闭右开,所以当 nums[mid] 被检测之

后,下⼀步应该去 mid 的左侧或者右侧区间搜索,即 [left, mid) 或 [mid + 1, right)。

4、为什么该算法能够搜索左侧边界?

答:关键在于对于 nums[mid] == target 这种情况的处理:

if (nums[mid] == target)

right = mid;

可⻅,找到 target 时不要⽴即返回,⽽是缩⼩「搜索区间」的上界 right,在区间 [left, mid) 中继续搜

索,即不断向左收缩,达到锁定左侧边界的⽬的。

5、为什么返回 left ⽽不是 right

答:都是⼀样的,因为 while 终⽌的条件是 left == right。

6、能不能想办法把 right 变成 nums.length - 1,也就是继续使⽤两边都闭的「搜索区间」?这样就可

以和第⼀种⼆分搜索在某种程度上统⼀起来了。

答:当然可以,只要你明⽩了「搜索区间」这个概念,就能有效避免漏掉元素,随便你怎么改都⾏。下⾯我

们严格根据逻辑来修改:

因为你⾮要让搜索区间两端都闭,所以 right 应该初始化为 nums.length - 1,while 的终⽌条件应该是

left == right + 1,也就是其中应该⽤ <=: