[LeetCode]Search for a Range

二分的做法，这里我们二分的时候如下处理：

• 找左边界的时候
• 如果A[mid] >= target, hi = mid - 1
• 如果A[mid] < target, lo = mid + 1
• 找右边界的时候
• 如果A[mid] <= target, lo = mid + 1
• 如果A[mid] > target, hi = mid - 1

跳出循环条件是 lo > hi，这样当循环结束时，对于左边界：

• 如果 target 在 array 中，那么 lo 对应的是左边界
• 如果 target 不在 array中
• lo 可能等于 A.length
• A[lo] 不等于 target

对于右边界来说是一样的，代码如下：

我们改一下 return 的策略也可以达到效果，如下代码如所示：

解释：

• 在找左边界的时候，hi 是左边界左边的那一个位置
• 在找右边界的时候，lo 是右边界右边的那一个位置
• 如果 left > right的时候，target 是不在 array里的

但是以上的代码仍然有很多重复的部分，为了消除重复的代码用同样的代码就可以搜索上下边界，我们需要对策略做一个很小的修改，对于上边界的话，我们寻找上边界右边的那一个数，那么对于右边界，情况会变为，假设输入数组长n，我们在[0,n]当中进行搜索：

• 如果A[mid] <= target, lo = mid + 1
• 如果A[mid] > target, hi = mid

这样上下边界就可以共用一套代码了，只要多一个bool来标记我们这次是寻找上边界还是下边界即可。代码如下：