Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
本题先对数组进行二分搜索，如果找到了目标元素就返回相应的index，如果最终没有找到对应的元素，则比较最后一个元素与目标元素的大小。实现代码如下：
1 public class Solution {
2 public int searchInsert(int[] A, int target) {
3 int length = A.length;
4 if (A.length == 0) return 0;
5 int i = 0, j = length - 1;
6 while (i < j) {
7 int mid = (i + j) / 2;
8 if (A[mid] == target) return mid;
9 if (A[mid] < target) {
10 i = mid + 1;
11 } else {
12 j = mid - 1;
13 }
14 }
15 return A[i] < target ? i + 1 : i;
16 }
17 }