35.Search Insert Position
===
### Description
(easy)
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

#### example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
#### example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
#### Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
#### Constraints:
- 1 <= nums.length <= 10^4^
- -10^4^ <= nums[i] <= 10^4^
- nums contains distinct values sorted in ascending order.
- -10^4^ <= target <= 10^4^

### 想法
c:題目要求在O(log n)解題所以是一個BST的題目，因為他給一個已經sort好的array，用BST上下夾很快就可以找到target，用左右邊去夾畫畫圖很快就可以找到應該insert 的位置。
python:用一樣的思維寫一次，主要是要用BST沒什麼比較快的方法

### 程式碼

#### c:

int searchInsert(int* nums, int numsSize, int target){
    int left=0;
    int right=numsSize-1;
    int mid=0;

    while(left<=right){
        mid=(left+right)/2;
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]<target){
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    return left; 
}

Runtime: 0 ms
Memory Usage: 6 MB
#### python:

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

Runtime: 47 ms
Memory Usage: 14.7 MB