LeetCode35搜索插入位置

发表于 | 更新于 | 分类于 |
搜索插入位置

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

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

示例 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
输入: [1,3,5,6], 0

解题思路：

使用二分查找来做这个问题。二分查找，要同时注意始末边界条件的处理。

二分查找时，需要注意左右边界的移动，边界移动+1或者-1

问题解答：

Github代码：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c35.py

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
34
35
36
37
38
class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums = [1, 2, 3, 4, 5]
        start = 0
        end = len(nums) - 1

        if target < nums[start]:
            return start
        if target > nums[end]:
            return end + 1

        if len(nums) == 1:
            if target > nums[0]:
                return 1
            else:
                return 0

        while start < end:

            if start + 1 == end:
                if nums[start] == target:
                    return start
                elif nums[end] == target:
                    return end
                return start + 1

            mid = (start + end) // 2
            if nums[mid] > target:
                end = mid
            elif nums[mid] < target:
                start = mid
            else:
                return mid