GuilinDev

Lc0035

05 August 2008

* 35 - Search Insertion Position

原题概述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2

Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2

Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2

Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2

Input: [1,3,5,6], 0
Output: 0

题意和分析

给一个升序数组，和一个目标值，寻找该目标值是否在数组里面，返回数组出现的index；如果没有，那么返回该target值升序应该出现的index。

1) 第一种方法是常规的Binary Search的方法，没什么好说的，Time：O(logn)， Space(1)；

2) 第二种办法从头往后找（当然从后往前找也是一样），因为是升序排好的数组，遇到相等的值返回当前index，如果大于了还没找到那也返回当前的index，后面当然是找不到了；Time：O(n)， Space(1)；

代码

背诵模板，感觉较麻烦一点，下面的老写法更简练

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        // 因为这个模板保证left和right不会相互越过，所以需要额外判断下超左边或右边的时候
        if (nums[left] > target) {
            return 0;
        } else if (nums[right] < target) {
            return right + 1;
        }
        
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (nums[right] == target) {
            return right;
        } else if (nums[left] == target) {
            return left;
        }
        
        return right;
    }
}

老写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return left;//如果没有找到，则最后left超过right值的地方是target应该处的位置，因为是“超过”，在当前的后一位
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return self.searchInsertHelper(nums, target, 0, len(nums) - 1)
    def searchInsertHelper(self, nums: List[int], target: int, left: int, right: int) -> int:
        if left > right:
            return left
        mid = left + (right - left) // 2
        if target == nums[mid]:
            return mid
        elif target < nums[mid]:
            return self.searchInsertHelper(nums, target, left, mid - 1)
        else:
            return self.searchInsertHelper(nums, target, mid + 1, right)

顺序找一遍

1
2
3
4
5
6
7
8
9
10

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;//target比所有数都大，放在最后一位
    }
}
This site is open source. Improve this page.