给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104
思路：题目中说必须使用时间复杂度为O(logN)的算法，再看提示部分nums为无重复元素的升序排列数组，已经提示出要使用二分查找了。
首先构建二分查找框架
int left = 0;
int right = nums.length-1;
int num=0;
while(left<right){
int mid = (left+right)/2;
...
}
此时观察提示，可以看出left+right不会造成溢出的情况。
既然是有序数组，就可以根据mid和target的大小，来决定向小数的方向折半，还是向大数的方向折半。所以就有了一下三种情况：
（1）当nums[mid]==target时，返回mid
（2）当nums[mid]>target时，left=mid+1
（3）当nums[mid]<target时，right=mid-1
即
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid+1;
} else if (nums[mid] > target) {
right = mid-1;
}
接下来看nums的长度，题上没有给，那默认为1到n，这时要考虑循环的终止条件left<right是否正确。
假设数组长度为1，那么left就等于right ， 很明显当left等于right时不满足while循环条件，所以不管target的值为多少最后都会返回-1。
继续考虑数组长度为2的情况，left<right可以进入循环，当数组长度为2时进入循环后mid值为0。但是当数组中出现target的值对应下标为1的话，无法通过left=mid+1找到，因为当mid+1就等于1。这时left=right，不满足left<right 所以会跳出循环返回-1。
很明显，少一次循环，此时就可以把while的条件改为left<=right，这样就可以完美的解决这个问题。
此时算法还没有结束，看题上要求，当目标值不存在数组中时，返回它将要插入的位置。
定义一个int类型数num=0
首先，既然数组中不存在该值，那么二分查找一定会运行到最后。那么我们到底要取最终的left还是最终的right。这里我们可以做一个实验。
再定义一个int类型数num2=0，让num2=right，num=left
就以第一组[1,3,5,6]为例，我们分别取0，4，7来验证最后取left还是right
当target=0时：left=0，right=-1
当target=4时：left=2，right=1
当target=7时：left=4，right=0
由此可以看出 要想返回目标值插入的位置，只需要返回left的最终值就可以了。
该算法时间复杂度O(logN)，空间复杂度O(1)
完整代码：
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
int num=0;
while(left<=right){
int mid = (left+right)/2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid+1;
num = left;
} else if (nums[mid] > target) {
right = mid-1;
}
}
return num;
}