# **作業 4 演算法之條條大路通羅馬**
>**作者：林芸筠**
>**學號：Ｄ１２２５５２９**
>**Email : [e-mail]**

---

## 搜尋演算法
[704. Binary Search](https://leetcode.com/problems/binary-search/solutions/)

---

### 二元搜尋法

int guessNumber(int n){
int left = 1;
int right = n;

    while (left <= right){
        int mid = left + (right - left) / 2;
        int result = guess(mid);

        if (result == 0){
            return mid;
        }
        else if( result == -1)
        {
            right = mid - 1;
            }
        else
            left = mid + 1;
    }
return -1;

}

取中間值並將非目標值的範圍淘汰，不斷循環直到找出正解

---

## 線性搜尋法

int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

簡單直接的去找尋目標值

---

## 排序演算法
[912. Sort an Array](https://leetcode.com/problems/sort-an-array/)

---

### Bubble sort（泡沫排序法）

void bubbleSort(vector<int>& nums){
    for(int i = nums.size() - 1; i >= 0; i--)
        for(int j = 0; j < i; j++)
            if(nums[j] > nums[j + 1]) 
                swap(nums[j], nums[j + 1]);
}

先由左至右兩兩一組比大小，將大的往右邊排，重複執行直到結束

---

### Insertion sort（插入排序法）

void insertionSort(vector<int>& nums){
    if(nums.size() == 0 || nums.size() == 1) return;
    for(int i = 1; i < nums.size(); i++){
        int tmp = nums[i];
        int j = i - 1;
        while(j >= 0 && nums[j] > tmp){
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = tmp;
    }
}

將目標值有順序的插入有序數列

---

### Quick sort (快速排序法)

void quickSort(vector<int>& nums, int l, int r){
    if(l >= r) return;
    int i = l; // cursor for final pivot location 
    for(int j = l; j <= r - 1; j++){ // nums[r] is chosen as the pivot
        if(nums[j] <= nums[r]){
            swap(nums[i], nums[j]);
            i++; // smaller or equal elements go to the left of i 
        }
    }
    swap(nums[i], nums[r]); // after swap, the pivot is nums[i]
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

隨便取一數當基準，將剩餘數分大、小兩類並重複執行直到結束

---

### Merge sort (合併排序法)

void merge(vector<int>& nums, int l, int m, int r){
    vector<int> tmp(r - l + 1);
    int i = l; // index for left subarray
    int j = m + 1; // index for right subarray
    int k = 0; // index for temporary array
    while(i <= m && j <= r){
        if(nums[i] <= nums[j]) tmp[k++] = nums[i++]; 
        else tmp[k++] = nums[j++];
    }
    while(i <= m) tmp[k++] = nums[i++];
    while(j <= r) tmp[k++] = nums[j++]; 
    for(i = 0; i < k; i++) nums[l + i] = tmp[i];
}

// mergeSort(nums, 0, nums.size() - 1);
void mergeSort(vector<int>& nums, int l, int r){
    if(l >= r) return;
    int m = l + (r - l) / 2; //middle index, same as (l+r)/2
    mergeSort(nums, l, m);
    mergeSort(nums, m + 1, r);
    merge(nums, l, m, r);
}

將數量二分至只剩單個數，在兩兩一組合併比較大小，再重新二分到剩單個數，直到結束

---