二分查找算法 为啥左闭右闭 right = mid -1； 左闭右开为right = mid

这是二分查找里最核心的内容之一。关键不是「左闭右闭」还是「左闭右开」而是mid 是否已经被证明不可能是答案。左闭右闭[left, right]区间定义[left, right]表示left 和 right 都是可能答案例如left 0; right n - 1;假设我们在找第一个 target 的位置当nums[mid] target时说明mid 可能就是答案例如nums [1,2,2,2,5] target 2第一次mid 2 nums[2] 2此时mid 可能是第一个2吗不知道。因为左边还有nums[1] 2所以我们要继续往左找。但是mid 本身不能丢理论上应该写right mid;但是如果这样写while(left right)可能死循环。例如left 1 right 1 mid 1执行right mid;得到left 1 right 1区间没缩小。永远循环。因此左闭右闭模板必须right mid - 1;把 mid 排除掉。虽然排除了 mid但别忘了return left;最终 left 会停在第一个满足条件的位置。左闭右开[left, right)区间定义[left, right)右边界不属于搜索区间。例如left 0; right n;循环while(left right)当nums[mid] target时mid 可能是答案所以不能丢。写right mid;为什么不会死循环因为这里区间是[left,right)假设left 3 right 4则mid 3执行right mid;得到left 3 right 3此时left right已经不成立。循环结束。不会死循环。本质区别左闭右闭区间包含 right所以right mid可能导致区间大小不变。必须right mid - 1保证缩小。左闭右开区间不包含 right所以right mid已经缩小了区间。因为[mid,right) → [mid,mid)区间长度直接变成 0。用图理解假设left3 right4 mid3左闭右闭[3,4] ^ mid执行right mid;得到[3,3]下一轮还是mid3可能卡住。所以要right mid - 1;变成[3,2]循环结束。左闭右开[3,4) ^ mid执行right mid;得到[3,3)区间为空。直接结束。所以可以记住区间循环条件左移右边界[left,right]left rightright mid - 1[left,right)left rightright mid原因是左闭右闭中mid仍在区间内必须用-1保证区间缩小。左闭右开中right本来就不在区间内right mid已经完成缩小同时保留了mid作为候选答案。这也是为什么你现在的findFirst()while (left right) { ... if (nums[mid] target) left mid 1; else right mid - 1; } return left;能够正确返回第一个 ≥ target 的位置lower_bound。