給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。
如果目標值不存在于數組中，返回它將會被按順序插入的位置。

示例 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

1. 方法一：首先本題思路，找到第一個大于等于target的元素位置，即插入位置。所以直接遍歷數組，找到第一個大于等于target的元素位置就是結果。但本題要求時間復雜度為log(n),那么需要進行優化。
2. 方法二：二分查找。算法思路：將數組分成兩份，left=0，mid=(left + right) / 2，right=length-1。根據mid與target的大小，進一步劃分區域。如果mid>target，說明target在0到mid之間。反之，在mid到length-1之間。將范圍縮小(left = mid + 1 或 right?= mid - 1 ), 繼續比較。本題可以用二分查找的思想，不過算法是查找相等數據，本題需要查找第一個大于等于的數據。
   1. 這里說明下為什么以left進行返回：
      本題結果即找到第一個大于等于target的元素。在二分查找的過程中，遇到的第一個mid對應元素，大于target時，mid對應的元素不一定是第一個大于target元素，只是二分查找過程中遇到的第一個。此時需要繼續縮小范圍就繼續比較。
      那么什么情況下是第一個呢？首先mid對應元素和target相等的時候直接返回mid位置，即插入位置。大于的情況，因為數組中不存在target，那么一定會遍歷到left==right==mid的時候，如果這個元素大于target，根據二分查找算法原理，此時right = mid - 1，left>right跳出循環，left即結果;如果這個元素小于target，left = mid+1，left>right跳出循環，left即結果(已經加1)。這里不管是大于還是小于，mid的其他位置都是已經確認了大于或小于target了。那么如果這個位置小于target，那么它后面的就是第一個大于target的，如果這個位置大于target那么他就是第一個大于target的。

// 方法一
class Solution {public int searchInsert(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}if (nums[0] > target) {return 0;}if (nums[nums.length - 1] < target) {return nums.length;}for (int i = 0; i < nums.length; i++) {if (nums[i] >= target) {return i;}}return nums.length;}
}

// 方法二
class Solution {public int searchInsert(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}if (nums[0] > target) {return 0;}if (nums[nums.length - 1] < target) {return nums.length;}int left = 0;int right = nums.length - 1;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}
}