LeetCode解題之Search Insert Position

原題

在一個有序數組中，如果目標數字存在，則返回它的下標，否則返回它應該插入位置的下標值。

注意點：

例子：

輸入: nums = [1, 3, 5, 6], target = 5
輸出: 2

輸入: nums = [1, 3, 5, 6], target = 2
輸出: 1

解題思路

又是一道二分搜索的題。分以下幾種情況：如果當前數字是目標數字，或者當前數字大於目標數字而它之前的數字小於目標數字，則返回當前下標；如果當前數字為最後一個且它比目標數字小，則返回當前下標的後一位。

AC源碼

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        start = 0
        end = length
        while start < end:
            mid = (start + end) // 2
            if nums[mid] == target or (nums[mid] > target 
                and (mid == 0 or nums[mid - 1] < target)):
                return mid
            if mid == length - 1 and nums[mid] < target:
                return mid + 1
            if nums[mid] < target:
                start = mid + 1
            else:
                end = mid


if __name__ == "__main__":
    assert Solution().searchInsert([1, 3, 5, 6], 5) == 2
    assert Solution().searchInsert([1, 3, 5, 6], 2) == 1
    assert Solution().searchInsert([1, 3, 5, 6], 7) == 4
    assert Solution().searchInsert([1, 3, 5, 6], 0) == 0

歡迎查看我的Python">Github來獲得相關源碼。