【LintCode 简单】60. 搜索插入位置

港控/mmm° 2022-11-26 07:40 132阅读 0赞

1.问题描述：

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

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

2.样例：

\[1,3,5,6\]，5 → 2

\[1,3,5,6\]，2 → 1

\[1,3,5,6\]， 7 → 4

\[1,3,5,6\]，0 → 0

3.代码：

我实现的方法，有点复杂

class Solution:
        """
        @param A: an integer sorted array
        @param target: an integer to be inserted
        @return: An integer
        """
    
        def searchInsert(self, A, target):
            # write your code here
            if A == [] or target <= A[0]:
                return 0
            for i in range(1, len(A)):
                if A[i] == target or A[i - 1] < target and target < A[i]:
                    return i
                elif target > A[i] and i + 1 == len(A):
                    return i + 1

另外看到一个更加简便的方法，使用enumerate来迭代A

def searchInsert2(self, A, target):
            # write your code here
            if len(A) == 0:
                return 0
            for i, num in enumerate(A):
                if target <= num:
                    return i
            return len(A)

本题的挑战难度是实现O(log(n)) 时间复杂度。非常明显是需要用二分法来实现，并且题目已知是一个有序的数组，所以可以使用二分搜索。

def searchInsert3(self, A, target):
            left, right = 0, len(A) - 1  # 初始化左右端点位置
            while left <= right:  # 当条件合法时
                mid = left + (right - left) // 2  # 获取中点，如果是偶数取靠左的位置
                if A[mid] == target:  # 找到该数
                    return mid  # 直接返回
                elif A[mid] > target:  # 如果当前位置数比插入值大
                    right = mid - 1  # 更新右端点
                else:  # 如果当前位置数比插入值小
                    left = mid + 1  # 更新左端点
            return left  # 返回插入位置，这里是左端位置

参考资料：

1. [https://blog.csdn.net/sinat\_24948419/article/details/88343465][https_blog.csdn.net_sinat_24948419_article_details_88343465]

2. [https://www.jianshu.com/p/d67f3443563e][https_www.jianshu.com_p_d67f3443563e]

[https_blog.csdn.net_sinat_24948419_article_details_88343465]: https://blog.csdn.net/sinat_24948419/article/details/88343465
[https_www.jianshu.com_p_d67f3443563e]: https://www.jianshu.com/p/d67f3443563e