35. 搜索插入位置

Posted on | In
Words count in article: 437 | Reading time ≈ 1

题目

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

请必须使用时间复杂度为O(log n)的算法。

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

示例1：

1
2
输入: [1,3,5,6], 5
输出: 2

示例2：

1
2
输入: [1,3,5,6], 2
输出: 1

示例3：

1
2
输入: [1,3,5,6], 7
输出: 4

示例4：

1
2
输入: [1,3,5,6], 0
输出: 0

提示：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 为 无重复元素 的 升序 排列数组
  • -10^4 <= target <= 10^4

解法

解法一：

Java

暴力破解。因为数组是有序的，直接遍历一趟数组，找到对应的插入位置。如果初始位置的值比target大，返回0.如果数组最后一个元素比target大，返回数组长度。

但时间复杂度不符合要求

1
2
3
4
5
6
7
8
9
10
11
12
public int searchInsert(int[] nums, int target) {
        if (0 == nums.length) {
            return 0;
        }

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

解法二：

二分查找。因为数组已经排序，所以可以通过二分搜索来找到target需要插入的位置。因为数组元素不重复，所以不用考虑相同元素的场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int searchInsert(int[] nums, int target) {
        if (0 == nums.length) {
            return 0;
        }

        return findIndex(nums, target);
    }

    private int findIndex(int[] nums, int target) {
        int result = nums.length;
        int begin = 0;
        int end = nums.length - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            if (target <= nums[mid]) {
                result = mid;
                end = mid - 1;
            } else {
            	begin = mid + 1;
            }
        }
        return result;
    }
0%