题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例1：
输入: [1,3,5,6], 5 输出: 2
示例2：
输入: [1,3,5,6], 2 输出: 1
示例3：
输入: [1,3,5,6], 7 输出: 4
示例4：
输入: [1,3,5,6], 0 输出: 0
题目难度：简单
分析：
题目可以分解成两步，1：查找元素是否在数组中。2：如果不存在找到合适的插入位置。因为数组是排序的，所以可以遍历或者二分。
代码如下：
解法一：遍历数组
class Solution { public int searchInsert(int[] nums, int target) { int length = nums.length; if (length == 0) { return 0; } // 遍历数组：如果迭代元素大于等于目标元素，直接返回下标即可 for (int i = 0; i < length; i++) { if (nums[i] >= target) { return i; } } // 如果前面的情况都不满足，说明目标元素大于所有的数组元素 return length; } }
小结：
时间复杂度为O(n)，需要遍历一次数组。
解法二：二分查找
class Solution { public int searchInsert(int[] nums, int target) { int length = nums.length; if (length == 0) { return 0; } // 二分搜索查找目标是否存在 int left = 0, right = 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; } } // 不存在，但是经过二分后可以知道left的位置 // 如果目标值大于数组中所有元素的话，此时nums[left]会越界 if (left == length) { return length; } // 经过二分后left会停留在最接近target值的位置上 if (nums[left] > target) { return left; } else { return left + 1; } } }
小结：
时间复杂度为O(logn)，二分查找比直接查找快。
总结：
看见排序数组和目标值查找的问题，应该第一时间想到是否可以用二分查找解决问题。
