思路1 二分查找

• 时间复杂度 O(n * logn)

• 空间复杂度 O(1)

如果target不在数组中的话，最后跳出循环时，low = high + 1，这时的low就是应该插入的位置。时间复杂度O(logn)

注意这道题实际跑出来的时间，顺序查找比二分查找要快。面试中一定要搞清楚面试官的意图。