LeetCode刷题-- 搜索插入位置

一、题目

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

你可以假设数组中无重复元素。

示例 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. 插入的元素比第一个元素还小，直接返回0
2. 插入的元素最大，直接返回nums.length
3. 插入的元素在数组中存在，返回该返回的下标
4. 插入的元素在数组中不存在，找到第一个比target大的数，该数的位置就是应该插入的位置。
   解题有两种思路： 第一种暴力破解法、第二种二分查找法

三、代码

public class _01_搜索插入位置 {

    // 1. 暴力法解决: 时间复杂度： O(n)   空间复杂度: O(1)         0ms,33.76MB
    public static int searchInsert(int[] nums, int target) {
        for(int i=0; i<nums.length; i++){
            if(target <= nums[i]){
                return i;
            }
        }
        return  nums.length;
    }
    
    // 2.  二分法解决
    public static int searchInsert2(int[] nums, int target) {
         int left = 0, right = nums.length-1;                 // target在左闭右闭的区间里
         while(left <= right){                       // 当left=right时,区间[left,right]仍然有效。
             int mid = left + (right - left)/2;     // 等同于 int mid = (left + right)/2;
             if(nums[mid] == target)
                 return mid;                         // 二分法查找到了target，对应第三种情况
             else if(nums[mid] < target){
                 left = mid + 1;
             }else if(nums[mid] > target){
                 right = mid -1;
             }
         }
      
         if(target < nums[0])       // 第1种情况
             return 0;
         return right +1;          //  此处用right加1可以涵盖第2和第4种情况 
    }

    public static void main(String[] args) {
        int [] nums = {1,2,3,5,6};
        int target = 7;
        System.out.println(searchInsert(nums,target) );
        System.out.println(searchInsert2(nums,target) );
    }
}

四、时间负载度和空间复杂度

暴力法： 时间复杂度O(n) ,空间复杂度O(1)

二分查找法：时间复杂度O(logn) ,空间复杂度O(1)