題目描述

給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。
你可以假設(shè)數(shù)組中無重復(fù)元素。
示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

輸入: [1,3,5,6], 0
輸出: 0

我的解法

由于數(shù)組已有序，所以直接進(jìn)行搜索，不過感覺對于開頭和結(jié)尾的處理有點(diǎn)繁瑣。

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target <= nums[0]:
            return 0
        for pos in range(len(nums)-1):
            if target > nums[pos] and target < nums[pos+1]:
                return pos+1
            elif target == nums[pos]:
                return pos
        if target > nums[-1]:
            return len(nums)
        elif target == nums[-1]:
            return len(nums)-1

最優(yōu)解法

從數(shù)組兩端同時(shí)向中間逼近。

class Solution:
    def searchInsert(self, nums, target):
        if not nums:
            return 0
        i = 0
        j = len(nums) - 1
        if j == 0:
            return 0 if nums[j] >= target else j + 1

        binaryIndex = (j - i + 1) // 2
        while i < j - 1:
            if nums[binaryIndex] < target:
                i = binaryIndex
            if nums[binaryIndex] > target:
                j = binaryIndex
            if target == nums[binaryIndex]:
                return binaryIndex
            binaryIndex = (j + i) // 2

        if target <= nums[i]:
            return i
        elif target <= nums[j]:
            return j
        else:
            return j + 1