LeetCode题解：搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不在数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为O(logn)的算法。

示例

• 示例1
  输入：nums = [1,3,5,6], target = 5
  输出：2
• 示例2
  输入：nums = [1,3,5,6], target = 2
  输出：1

方法思路

二分查找法

利用双指针left和right，分别指向数组左边界和右边界。每次遍历都重新计算中间位置mid，当目标值小于或等于nums[mid]时，right左移到mid-1位置，否则left右移到mid+1位置。如此当出现while(left<=right)结束条件时，得到需求的位置。

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

复杂度分析

• 时间复杂度：O(logn)，其中n为数组的长度。二分查找所需的时间复杂度为O(logn)。
• 空间复杂度：O(1)，我们只需要常数空间存放若干变量。

暴力破解

暴力破解法虽然不满足时间复杂度O(logn)的条件，但也是我们最易想到的。

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