給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

請必須使用時(shí)間復(fù)雜度為 O(log n) 的算法。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

輸入: nums = [1], target = 0
輸出: 0

提示:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 為無重復(fù)元素的升序排列數(shù)組
• -10^4 <= target <= 10^4

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-insert-position

Python3

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)-1
        while low <= high:
            mid = (low+high)//2
            guess = nums[mid]
            if guess == target:
                return mid
            elif guess < target:
                low = mid + 1
            else:
                high = mid -1 
        return low