Common algorithms for array 常見字串演算法 - paulip114/blog GitHub Wiki

1. Binary Search O(log n)

Binary Search 基本形態

// 迴圈（Loop）
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// 遞迴 （Recursive） 
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1;
    }

    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

// Example usage
let sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
let targetValue = 9;

let result = binarySearch(sortedArray, targetValue);

有時候使用 Binary Search 的時候，會需要從主程式用 迴圈（Loop）的方式重複 call Binary Search function 這時候要考慮到 left right 會因爲每次而變動，所以要將他們以 參數（Parameter） 的方式帶進 function

function main(array: number[], target: number): number {
    for(...) {
        binarySearch(...)
    }
    function binarySearch(left: number, right: number, target: number): number {
        ...
    }
    return ...
}

用途：Leetcode 167. Two Sum II - Input Array Is Sorted

2. Two pointers O(n)

Two pointers 基本形態

function twoSum(numbers: number[], target: number): number[] {
    let left = 0; // Pointer at the start of the array
    let right = numbers.length - 1; // Pointer at the end of the array

    while (left < right) {
        const sum = numbers[left] + numbers[right];

        if (sum === target) {
            return [left, right];
        } else if (sum > target) { // too large so decrease from right (array is sorted, the rightest number is largest)
            right--;
        } else {
            left++;
        }
    }
    return [];
}

// Example usage
let sortedArray = [2, 7, 11, 15];
let targetValue = 9;

用途：Leetcode 167. Two Sum II - Input Array Is Sorted

Sliding Window - Two pointers 之中的一個分支

3. Hash Map O(n)

Hash Map 基本形態

function twoSum(numbers: number[], target: number): number[] {
    // Utilizing Hash map
    const dict: Record<number, number> = {} // Hash map <number, index>

    for (let i = 0; i < numbers.length; i++) {
        const tempTarget = target - numbers[i]
        if (tempTarget in dict) { // find if the target exit in dict
            return [dict[tempTarget] + 1, i + 1]
        }
        dict[numbers[i]] = i // if not found in dict, add the current number and index into dict
    }
    return []
};
  1. 先 Declare 一個 Record type 的 dictionary const dict: Record<number, number> = {}
  2. 在 Loop 裏面從左到右逐一查找當前數值的（tempTarget)
  3. 如果 dict 裏面有 tempTarget， 就可以 return 當前數值的 index 以及 tempTarget index（這個 case 因爲需要 return 從 1 開始的 index 所以需要 + 1）
  4. 如果 dict 裏面沒有 tempTarget，就將當前的 value 和 index 塞入 dict

用途：Leetcode 167. Two Sum II - Input Array Is Sorted

針對已經排序 和 未排序 的 array 應該選擇什麽搜尋方式

處理 已經排序 和 未排序 的 array，選擇正確的搜尋方式會大大影響效率。以下是清楚的對比：

🔍 搜尋方法比較表

情況 推薦搜尋法 時間複雜度 備註
✅ 已排序的 array 二分搜尋 (Binary Search) / 兩指針 (Two Pointers) O(log n) / O(n) 前提是 array 是升序排列
❌ 未排序的 array Hash Map（雜湊表）搜尋 O(1) 查找 / O(n) 總時間 適用於如 Two Sum 等問題

✅ 已排序 Array

🔹 適用演算法：

  1. Binary Search（二分搜尋）

    • 適合找單一元素，例如：「找數字 8 是否在 array 裡」
    • 時間複雜度：O(log n)
    • 前提：array 必須是升序或降序排序過

  2. Two Pointers（雙指針）

    • 適合解像 Two Sum / 合併兩個區間 等問題
    • 從左、右兩端一起掃描，根據條件推進指針
    • 時間複雜度：O(n)

❌ 未排序 Array

🔹 適用演算法：

  1. Hash Map（雜湊表）

    • 適合搜尋配對值、檢查是否存在某個值
    • 範例：Two Sum — 建一個 Map<number, index>
    • 時間複雜度：O(n) 建表 + O(1) 查找

  2. Linear Search（線性搜尋）

    • 最基本方法，從頭走到尾
    • 時間複雜度：O(n)
    • 適合小資料量 / 懶得用 Map 的情況

🧠 總結

Array 狀態 搜尋目標 推薦方法
已排序 找一個值 Binary Search
已排序 找兩數之和 / 區間條件匹配 Two Pointers
未排序 找兩數之和 / 配對、重複等 Hash Map
未排序 單純找值（小資料量） Linear Search