###### tags: `Leetcode` `easy` `binary search` `python` `c++` `Top 100 Liked Questions`

# 35. Search Insert Position

## [題目來源:] https://leetcode.com/problems/search-insert-position/

## 題目:
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.**

## 解題想法:
看到O(log n): 多半往二分法思考

## Python:

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        '''
        O(log n) runtime complexity. -> 對半分
        #二元搜尋Binary Search!!!!
        '''
        head=0
        tail=len(nums)-1
        while head<=tail:
            mid=tail+(head-tail)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                tail=mid-1
            else:
                head=mid+1
        return head

if __name__ == '__main__':
    result=Solution()
    ans=result.searchInsert(nums = [1,3,5,6], target = 5)
    print(ans)

## C++:

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int head = 0;
        int tail = nums.size() - 1;
        while (head <= tail)
        {
            int mid = tail + (head - tail) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target)
                tail = mid - 1;
            else
                head = mid + 1;
        }
        return head;
    }
};

int main()
{
    vector<int> nums = {1, 3, 5, 6};
    int target = 5;
    Solution res;
    int ans = res.searchInsert(nums, target);
    cout << ans << endl;
    return 0;
}