资料内容:
3、为什么 left = mid + 1,right = 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,也就是其中应该⽤ <=: