如何正确判断二分边界？

常见问题

1. while 内条件是 (leq) 还是 (<)
2. left 和 right 的修改时用不用加 (1) 减 (1)

例题分析

例：
给定一个正整数 (n( 1 leq n leq 1,000))。

第二行输入 (n) 个整数 (num_i(0 leq num_i leq 10,000))，保证严格单调递增，第三行输入一个整数 (k( 0 leq k leq 10,000))。

若数列中有与 (k) 相等的数，输出其下标，否则输出 No。

一般来说，我们将二分分为左闭右闭，左闭右开两种类型。

左闭右闭

首先我们根据上面容易出现的两个问题进行分析。

1. 因为当出现 left == right 是有意义的，所以 while 内使用 left <= right
2. 如果 num[mid] > k 成立，则下标超过 mid 的数（包括 mid）都不正确，因此 right = mid - 1。
   若是不成立，也不能判断 num[mid] 是否等于 k，所以不能使 left = mid + 1，而是 left = mid。
   不过在此题中可以直接判断是否相等，相等直接输出值即可。

左闭右开

还是根据上面两个容易出错的地方分析。

1. 在左闭右开的区间里，left == right 没有意义，所以 while 内使用 left < right
2. 如果 num[mid] > k 成立，又由于区间是左闭右开的，所以可以直接使 right = mid。不成立时和上面左闭右闭的相同。

总结

在做题中要严格按照区间和步骤去思考，避免不必要的问题。