最近又上了這門課程－資料結構與演算法 (JavaScript)，一樣附上 Udemy 課程連結給有需要的人參考唷！這門課是全中文授課的，如果對於自己的英文能力沒那麼有把握的話可以選擇這門課程，教得很好懂唷！這篇文章的重點會著重在 Linear Search 線性搜尋法 與 Binary Search 二分搜尋法這兩種演算法，也會分享 Wilson 在課程中特別分享的 Counter 與 Pointer 兩種常見的解題技巧。

先看看這張圖，大概就可以理解這兩個演算法的差異：
Algorithm

什麼是演算法？

什麼是演算法？來看看牛津字典的定義吧！”A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.” 演算法是一個有序、有步驟與規則的計算過程，而這個計算過程能幫助我們解決特定問題。

演算法也會有效能與適用在解決不同問題的差異，而演算法的效能會以「空間複雜度」以及「時間複雜度」作為評估標準，想了解空間複雜度可以參考這篇文章唷！Master the Coding Interview (1) - BigO 時間複雜度

Linear Search (線性搜尋法)

Linear Search 線性搜尋法大概是這門課程中最好懂的演算法了，線性搜尋法簡單來說就是從頭到尾一個個的搜尋，直到找到目標為止，例如下方的程式碼，就是遍歷 Array 中的每一個位置直到找到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17];

const LinearSearch = (arr, n) => {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === n) {
            return i;
        }
    }
    return -1;
};

LinearSearch(arr, 13);
// 6 answer

Linear Search 的時間複雜度：

1. Worst Case：O(n) 答案很慘的在第 n 個位置
2. Best Case：O(1) 答案很讚的在第 1 個位置
3. Average Case：O(n/2)

Binary Search (二分法)

Binary Search 二分法顧名思義就是不斷地分成兩部分再去針對特定一半做搜索。以下方的函式為例，當我們要在一個 Array 中找到目標數值，我們可以先將 Array 從中切開，取中間數值跟目標數值比對，刪去不可能的一半，再繼續對半，以此類推可以一直省去不必要的運算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17];

const BinarySearch = (arr, n) => {
    let min = 0;
    let max = arr.length - 1;

    while (min <= max) {
        let middle = Math.floor((min + max) / 2);
        if (n > arr[middle]) {
            min = middle + 1;
        } else if (n < arr[middle]) {
            max = middle - 1;
        } else if (n === arr[middle]) {
            return middle;
        }
    }
    return -1;
};

BinarySearch(arr, 17);

BinarySearch 的時間複雜度：

1. Worst Case： O(log n)
2. Best Case： O(1) 答案在 1/2 的位置
3. Average Case： O(log n)

二分法範例題：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const averagePair = (array, avg) => {
    let left = 0;
    let right = array.length - 1;
    let result = [];

    while (right > left) {
        let temp = (array[right] + array[left]) / 2;
        if (temp > avg) {
            right--;
        } else if (temp < avg) {
            left++;
        } else if (temp === avg) {
            result.push([array[right], array[left]]);
            right--;
            left++;
        }
    }

    return result;
};

averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);
// [ [ 14, -11 ], [ 3, 0 ], [ 2, 1 ] ] answer

接著是兩個衍伸出來非常實用的解題技巧，分別是 Counter 與 Pointer（Wilson 有提到這樣的概念其實有很多種名稱，只是在這門課程裡用 Counter 與 Pointer 作為技巧名字。）

解題技巧 1：Counter

Counter 就是建立一個計算區 (object)，透過 key and value pair 的方式暫時記著要運算的數值，最後在從 key and value pair 中取得我們要的答案，這樣可以簡化運算的歷程。

1. General Skill when doing algorithm design
2. Using a counter object will reduce the complexity of algorithm

(1) 範例題：Frequency Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const SameFrequency = (string1, string2) => {
    const arr1 = string1.split('');
    const arr2 = string2.split('');

    if (arr1.length !== arr2.length) {
        return false;
    }

    let counter1 = {};
    let counter2 = {};

    for (let i = 0; i < arr1.length; i++) {
        if (counter1[arr1[i]]) {
            counter1[arr1[i]]++;
        } else {
            counter1[arr1[i]] = 1;
        }
    }

    for (let i = 0; i < arr2.length; i++) {
        if (counter2[arr2[i]]) {
            counter2[arr2[i]]++;
        } else {
            counter2[arr2[i]] = 1;
        }
    }

    for (let property in counter1) {
        if (!counter2[property]) {
            return false;
        }
        if (counter2[property] !== counter1[property]) {
            return false;
        }
    }
    return true;
};

// counter1 { a: 2, b: 1, c: 1 }  counter2 { a: 1, b: 2, c: 1 }
SameFrequency('aabc', 'abbc');
// false answer

解題技巧 2：Pointer

Pointer 中文是指標、定位的意思，Pointer 常用在解 string 或是 array 比對的考題中，我們可以透過定位指出特定位置的數值與另一個位置的數值做比對，像第一題 Palindrome 對稱題，就是第一個位置與最後一個位置比對，接著是第二個位置與倒數第二個位置做比對，以此類推，這樣的解法就是運用 Pointer 的概念。

(1) 範例題：Palindrome （判斷單詞是否對稱）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const palindrome = (str) => {
    let left = 0;
    let right = str.length - 1;

    while (left <= right) {
        if (str[left] === str[right]) {
            right--;
            left++;
        } else {
            return false;
        }
    }
    return true;
};

palindrome('tacocat'); //true
palindrome('hsuan'); //false
palindrome('madam'); //true

圖解 Pointer 概念：
Algorithm

接下來這一題 Subsequence Problem 比較複雜，因為題目允許刪除中間多餘的字串，我們一樣把兩個 array 第一個位置的數值做比對，但是當值不同時，與之比對的字串就要往下再移一個位置去做比對，直到找到對應的值為止。

(2) 範例題：Subsequence Problem 判斷長字串中是否包含段字串的字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const isSubsequence = (str1, str2) => {
    if (str1.length === 0) {
        return true;
    }

    let pointer1 = 0;
    let pointer2 = 0;

    while (pointer2 < str2.length) {
        if (str1[pointer1] === str2[pointer2]) {
            pointer1++;
        }
        if (pointer1 >= str1.length) {
            return true;
        }
        pointer2++;
    }
    return false;
};

isSubsequence('hello', 'hello World'); //true
isSubsequence('book', 'brooklyn'); //true
isSubsequence('abc', 'bac'); //false

以上就是資料結構與演算法 (JavaScript) (1) - Linear Search & Binary Search 的課程摘要與練習題，很好我們一腳踏進演算法的世界了 XD

參考文章：https://tw.alphacamp.co/blog/algorithm-introduction