[LeetCode] 35题 搜索插入位置(Search Insert Position)

作者 做棵大树 日期 2019-05-19
[LeetCode] 35题 搜索插入位置(Search Insert Position)

搜索插入位置(Search Insert Position)

题目要求

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。


示例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. 遍历整个数组 ( 最优时间复杂度O(1),最坏O(n) )

    int len = nums.length;
    if (len == 0) return 0; // if the nums is empty, return 0
    for(int i = 0; i < len; i++) {

    if(target <= nums[i]) {  //  when target <= nums[i] , return
        return  i;
    }
    

    }
    return len;

  1. 二分法进行查找 ( 2的logn次方等于n,最坏时间复杂度为O(logn),最优O(1) )

    int head = 0;
    int tail = nums.length;
    int mid = 0;
    if( nums.length == 0 || target <= nums[head]) return 0;
    while(head < tail) {

    mid = ((tail - head) >> 1) + head;
    if(target > nums[mid]) {
        head = mid + 1;
    }else{
        tail = mid;
    }
    

    }
    return tail;