讨论/《数组和字符串》 - 搜索插入位置/
《数组和字符串》 - 搜索插入位置

最简单的思路

  1. 如果数组中的值大于或者等于target,直接return
  2. 如果全部遍历完证明target是最大的数,直接插入末尾

java

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;
    }
}

image.png

缺点:数值较多时,没有那么高效,因此可以引入二分查找

二分查找:

  1. left=0,right=nums.length,取mid为中间值
  2. 如果nums[mid]==target,返回mid值,循环终止
  3. 如果nums[mid]>target,就说明从mid到right之间的值都是“无用的”需要挪动right,而我们能知道的接近的一个无用的值是mid,因此right必须比mid还要小才行,也即是right=mid-1;
  4. 同理,left=mid+1;
  5. 一直循环,除非找到mid值或者发现target根本不在目标中,也就是已经完全循环了一遍(left>right),这时候的left的值就是最接近target但又大于target的值(可以拿0来举例自己画一遍过程),因此return left
1
展开全部 40 讨论