# 35. [Search Insert Position](https://leetcode.com/problems/search-insert-position/)

## Description
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.


## Methodology
因為需要O(log n)的時間複雜度，所以從頭一個一個開始比較會太慢O(n)，所以我想利用binary search的方式來找尋插入點。

### Binary Search
定義: 在一個排序好的數列，找尋某個Target，找到回傳其index，否則回傳-1。

#### 程式範例(C code)

#include <stdio.h>

int len(int list[]) {
    int size = 0;
    for (size; list[size] != '\0'; size++) {
        ;
    }
    return size;
}

int binary_search(int num_list[], int target, int size) {
    
    int left = 0;
    int right = size - 1;
    //printf("right = %d\n", right);
    int mid;
    
    while (left <= right) {
        mid = (left + right)/2;
        //mid = left + (right - left)/2;
        if (num_list[mid] < target) {
            left = mid + 1;
        }
        else if (num_list[mid] > target) {
            right = mid - 1;
        }
        else {
            return mid;
        }
    }
    return -1;
}

int main()
{
    /*
    test cases:
    1. num_list[] = {1, 2, 3, 4, 5, 6} - pass
    2. num_list[] = {1, 2, 5, 7, 9, 10, 15, 32, 45} -pass
    3. num_list[] = {1} - pass
    4. num_list[] = {} - pass
    */
    //note: 原本沒指定array size是50，想直接給編譯器處理結果有些數字範圍會怪怪的，所以給定一個50。
    int num_list[50] = {};      
    int target, i, size;
    
    size = len(num_list);
    printf("The number list is:");
    for (i = 0; i < size; i++) {
        printf(" %d ", num_list[i]);
    }
    printf("\n");
    
    printf("What number do you want to search? ");
    scanf("%d", &target);

    if (binary_search(num_list, target, size) != -1) {
        printf("target is in number %d\n", binary_search(num_list, target, size));
    }
    else {
        printf(" -1, there is no target in the list.\n");
    }
    
    return 0;
}

#### 延伸問題: 如何避免mid溢位?
Ans:
使用`mid = left + (right - left)/2`的方式，不要用`mid = (left + right)/2`，相加可能導致溢位。

#### 複習[array size](https://www.geeksforgeeks.org/length-of-array-in-c/)用法
1. sizeof

data_type size = sizeof(Array_name) / sizeof(Array_name[index]);

2. pointer arithmetic

data_type length = *(&arr + 1) - arr;

這邊觀念不太懂。

3. loop

int arr_length(int arr[])
{
    int i;
    int count = 0;
    for(i=0; arr[i]!='\0'; i++)
    {
        count++;
    }
    return count;
}

## Python
### Solution 01
| Runtime | Memory |
|---|---|
|31ms|14.1MB|

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        left = 0
        right = len(nums) - 1
    
        while (left <= right) :
            mid = int((left + right)/2)
            if (target < nums[mid]) :
                right = mid - 1
            elif (target > nums[mid]) :
                left = mid + 1
            else :
                return mid
        
        if (target < nums[mid]) :
            return mid
        else :
            return mid + 1 

### Solution 02
| Runtime | Memory |
|---|---|
|21ms|14.3MB|

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        left = 0
        right = len(nums) - 1

        # Speed up some boundary condition
        if (target < nums[left]):
            return left
        elif (target > nums[right]):
            return right + 1
    
        while (left <= right) :
            mid = int((left + right)/2)
            if (target < nums[mid]) :
                right = mid - 1
            elif (target > nums[mid]) :
                left = mid + 1
            else :
                return mid
        
        if (target < nums[mid]) :
            return mid
        else :
            return mid + 1

## C++

lass Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;

        //Speed up some boundary conditions
        if (target < nums[left]) {
            return left;
        }
        else if (target > nums[right]) {
            return right + 1;
        }

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

        if (target < nums[mid]) {
            return mid;
        }
        else return mid + 1;
    }
};

:::warning
vector型態中，只有size()可以用；若是string型態，則可以用length() or size()。
:::
### 複習:向量傳遞
1. 有&

#include <iostream>
#include <vector>

using namespace std;

void myFunction(std::vector<int>& nums) {
    //完整傳遞向量，可以直接用nums來修改及操作。
    nums.push_back(42);
}

int main() {
    std::vector<int> myVector = {1, 2, 3};
    cout << "The vector myVector contains: " << flush;
    for (int i = 0; i < myVector.size(); i++) {
        cout << " " << flush;
        cout << myVector[i] << flush;
    }
    
    cout << endl;
    
    myFunction(myVector);  //傳遞向量
    // 現在myVector包含 {1, 2, 3, 42}
    cout << "After calling funtion, the vector myVector contains: " << flush;
    for (int i = 0; i < myVector.size(); i++) {
        cout << " " << flush;
        cout << myVector[i] << flush;
    }
    return 0;
}

2. 沒有&