# 簡單演算法
* [name=Ivy Lin]
* [回首頁](https://hackmd.io/Qu2e9pQNSHC-e58Vp3ObhQ)

## 【簡介】

* **活用遞迴**
1. 通常快速排序的做法都包含一定程度的遞迴
2. 注意方法適用的範圍或數值

## 【經典演算】

### Binary Search

:::info
* **敘述**
>在一個排序過後的數列中找尋某個指定的數。
>(補充)時間複雜度是O(log2N)
:::

* **思路**
>1. 切半討論=>大於往右找、小於往左找
>2. 停止=>當範圍超過時即停止搜尋

* **程式**

#include <stdio.h>
int data[] = {1, 7, 9, 10, 27, 41, 60, 75, 89, 100};

void search(int s, int l, int r)
{
    int mid = (l + r) / 2;
    if (l > r)
        printf("Not in the data\n");
    if (data[mid] > s)
        search(s, mid + 1, r);
    if (data[mid] < s)
        search(s, l, mid - 1);
    if (data[mid] == s)
        printf("data[%d]=%d\n", mid, s);
}

int main()
{
    int s;
    scanf("%d", &s);
    search(s, 0, 9)

        return 0;
}

### Merge Sort

:::info
* **敘述**
>排序未被整理資料的一種方法
>(補充)時間複雜度是O(NlogN)
:::

* **思路**
>1. 屬於Divide and Conquer演算法，把問題先拆解(divide)成子問題，
>逐一處理子問題後，將子問題的結果合併(conquer)，如此便解決了原先的問題。
>2. 一樣利用"對半拆"的方式拆解資料

* **程式**

**遞迴寫法**

#include <stdio.h>
int input[100];
int left[55];
int right[55];
void paste(int l, int r, int m)
{
    int n1 = m - l + 1;
    int n2 = r - m;
    for (int i = 0; i < n1; i++)
        left[i] = input[l + i];
    for (int i = 0; i < n2; i++)
        right[i] = input[m + i + 1];

    left[n1] = 2147483647;
    right[n2] = 2147483647;

    int i = 0, j = 0;
    for (int k = l; k <= r; k++)
    {
        if (left[i] <= right[j])
            input[k] = left[i++];
        else
            input[k] = right[j++];
    }
}
void merge_cut(int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        merge_cut(l, m);
        merge_cut(m + 1, r);
        paste(l, r, m);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &input[i]);

    merge_cut(0, n);

    printf("(%d", input[0]);
    for (int i = 1; i < n; i++)
        printf(",%d", input[i]);
    printf(")\n");
    return 0;
}

**加入指標寫法**

#include <stdio.h>
int left[55];
int right[55];
void paste(int *input, int l, int r, int m)
{
    int n1 = m - l + 1;
    int n2 = r - m;
    for (int i = 0; i < n1; i++)
        left[i] = *(input + l + i);
    for (int i = 0; i < n2; i++)
        right[i] = *(input + m + i + 1);

    left[n1] = 2147483647;
    right[n2] = 2147483647;

    int i = 0, j = 0;
    for (int k = l; k <= r; k++)
    {
        if (left[i] <= right[j])
            *(input + k) = left[i++];
        else
            *(input + k) = right[j++];
    }
}
void merge_cut(int *input, int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        merge_cut(input, l, m);
        merge_cut(input, m + 1, r);
        paste(input, l, r, m);
    }
}

int main()
{
    int n;
    int input[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &input[i]);

    merge_cut(input, 0, n);

    printf("(%d", input[0]);
    for (int i = 1; i < n; i++)
        printf(",%d", input[i]);
    printf(")\n");
    return 0;
}