34. Find First and Last Position of Element in Sorted Array

Solution idea

非常经典的 Binary Search 类型题.

要点！！！

一定！一定！一定要明确target可能在数组中没有出现的三种情况，才能正确地写出post-processing中边界的查看条件!!!

• 情况一: target 不在数组范围中，target 过于小，在左边界以外. e.g. 数组{3, 4, 5}，target为2
• 情况二: target 不在数组范围中，target 过于大，在右边界以外，e.g. 数组{3, 4, 5}，target为6
• 情况三: target 在数组范围中，只是数组中不存在. e.g. 数组{3, 6, 7}, target为5

Time complexity = $O(\log n) + O(\log n) = O(\log n)$