# Leetcode 35 Binary search and insert
My Solution 時間O(log n) 空間 O(1)
---

def searchInsert(self, nums, target):
    high = len(nums)-1 # 字串最大index
    low = 0 # index從0開始
    while low <= high:
        mid = high + low // 2 # 取整數
        if target > nums[mid]: # 代表target在此數後
            low = mid + 1
        elif target < nums[mid]: # 代表target 在此數前
            high = mid -1 
        elif target == nums[mid]: # 找到target在nums index
            return mid
    # 如果最後找不到，要將target 插入對的位置
    if target > nums[mid]:
        return mid+1
    elif target < nums[mid]:
        if mid == 0:
            return 0
        else:
            return mid-1

###### tags: `LeetCode` `binary_search` `insert`