# 【LeetCode】 35. Search Insert Position

## Description
> Given a sorted array 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 may assume no duplicates in the array.

> 給一個排序過的陣列和一個目標數字，如果目標在陣列中，回傳它的索引值；否則請回傳它應該被插入的位置。

## Example:

Example 1:

Input: [1,3,5,6], 5
Output: 2


Example 2:

Input: [1,3,5,6], 2
Output: 1


Example 3:

Input: [1,3,5,6], 7
Output: 4


Example 4:

Input: [1,3,5,6], 0
Output: 0

## Solution

* 線性搜尋，遇到小於或等於的數字就回傳，否則回傳陣列的尾巴。

### Code

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++)
            if(target<=nums[i]) return i;
        return nums.size();
    }
};

---

* 在 2023/02/20 這天剛好看到每日題目又出了這題，發現題目中多了一個要求
* 請在 `O(log n)` 之內完成
* 用之前線性搜尋的方法一定是 `O(n)`，因此要改用二分搜尋
* 概念上跟一般的二分搜尋沒什麼不同，但要注意沒有 hit 到的時候，要考慮最後的數字應該放在哪邊
* 和最後的位置比大小，考慮放在它的左或右

class Solution {
public:
    int binarySearch(vector<int>& nums, int target, int low, int mid, int high)
    {
        if(nums[mid] == target) // hit
            return mid;
        else if(low >= high) // done
        {
            mid = (low + high) / 2;
            return mid + (nums[mid] < target);
        }
        else if(nums[mid] > target) // go left
            return binarySearch(nums, target, low, mid / 2, mid - 1);
        else // go right
            return binarySearch(nums, target, mid + 1, (mid + high + 1) / 2, high);
    }
    int searchInsert(vector<int>& nums, int target) {
        return binarySearch(nums, target, 0, nums.size() / 2, nums.size() - 1);
    }
};

###### tags: `LeetCode` `C++`