LeetCode-35.搜索插入位置

原题：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

（请必须使用时间复杂度为 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

---

这道题我给想复杂了，这里仅仅需要的是插入的位置，并不需要对整个数组进行排序。逐个去对比每个元素是否相等的操作实在有点傻。

• 当目标值小于数组中的最大元素时，可以在遍历中进行比较，当某个元素大于目标值时，直接将当前的索引返回，不需要再去管后面的数组怎么放置。
• 当目标值大于数组中的最大元素时，该元素自然就会放在数组的最后一个位置，即数组的长度值。

这里有一个点就是不需要去新建一个数组、想着把旧数组的值存入新数组，这样很傻，效率也很低，内存使用更多……这也就是评论区说取巧的地方。原数组length为5，最大index为4，插入目标值后新数组length为6，最大index为5，因此对于数组来说，新加入一个元素，新元素的索引值就是原数组的length。取巧就是取的数组规则的巧，元素的索引永远比它所在的长度-1。

class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=target) return i;
        }
        return nums.length;
    }
}