# 35. Search Insert Position 筆記

題目：給定一個排序好的陣列，並且不重複，找到target就回傳index，找不的話就回傳應該插入在哪邊。

時間複雜度必須為O(log n)

就是典型的Binary Search，一種在有序陣列中搜尋某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。

實作流程：排序過的陣列，搜尋中間值mid，mid的右邊比他大，左邊比他小，如果mid==target就輸出index，如果mid>target，答案只能在mid左邊。

等於說每次都砍一半，故稱為二元搜尋法。比對次數就是陣列長度就是2的幾次方，所以符合題意O(log n)

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) {
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return left;
}

###### tags: `LeetCode`