[LeetCode]Search Insert Position

Binary Search，最后lo的位置就是插入应该在的位置。
证明：当lo == hi的时候跳出循环，这时候有三种情况：

• lo的位置的值正好就是target，这时候直接return，就是我们要找的位置
• lo的位置的值大于target，这时候执行hi  = mid - 1，然后跳出循环，这个时候lo的位置也是插入的时候应该在的位置，因为target小是小于A[lo]位置最大的值，target应该被插入后应该在lo的位置
• lo的位置的值小于target，这时候执行lo = mid + 1然后跳出循环。由于现在target是大于A[lo]的最小值，插入后应该在的位置是上一次循环lo的后面(现在lo = mid  +1)，所以就是lo现在的位置。

代码如下：