[演算法] Binary Search：在陣列中尋找特定元素

Binary Search - LeetCode 704

資訊

• Leetcode
• Neetcode
• [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub

問題描述

透過 binary search 的方式在一個陣列（numArray）中找出目標元素（target）：

function binarySearch(numArray, target) {...}

演算法實做

在 Big O Notation & Time Complexity 時，曾有使用 while 迴圈寫過一個 binary search 的函式。在這裡我們則要練習使用 遞回函式(recursion) 的方式來撰寫這個函式。

在使用遞回函式時有一個要注意的地方是， 當一個函式裡面呼叫另一個函式時，需要等待裡面的這個函式執行完後才會跳出來繼續執行原本函式的內容 ，因此在寫判斷式時需要特別留意執行的順序。

完整程式碼

在使用 Binary Search 時，記得要先將陣列元素排序。

方法一：使用 two-pointer

var search = function (nums, target) {
  let l = 0;
  let r = nums.length - 1;

  // 1. 為什麼是 l <= r，而不是 l < r？
  while (l <= r) {
    const m = Math.floor((l + r) / 2);
    const midNum = nums[m];

    if (midNum < target) {
      // 2. 為什是 l = m + 1 而不是 l = m
      l = m + 1;
    } else if (midNum > target) {
      r = m - 1;
    } else {
      // midNum === target
      return m;
    }
  }

  return -1;
};

1. 為什麼是 l <= r，而不是 l < r？

   如果 nums = [1]，而且 target = 1 時，l = r = 0，這時候不會竟然迴圈中，為了確保能處理到這個情況，因此 while 中的條件是 l <= r。

2. 為什是 l = m + 1 而不是 l = m？

   從下圖可以看出每次改變 left 或 right 時，要加一或減一的原因。如果沒用加減一，當 target 不存在 nums 中時（例如，當 target = 4 時），會跳不出迴圈。

方法二：使用 recursive

function binarySearch(numberArr, target) {
  // 取得陣列中間的 index
  let middleIndex = Math.floor(numberArr.length / 2);

  // 如果找到就回傳 true
  if (numberArr[middleIndex] === target) {
    return true;
  }

  // 如果還沒找到，而且 numberArr 只剩一個元素，表示找不到
  if (numberArr.length === 1) {
    return false;
  }

  // 如果還沒找到
  if (target > numberArr[middleIndex]) {
    // 且 target 大於中間的數值，則取後半段的陣列再搜尋
    return binarySearch(numberArr.slice(middleIndex, numberArr.length), target);
  } else if (target < numberArr[middleIndex]) {
    // 且 target 小於中間的數值，則取前半段的陣列再搜尋
    return binarySearch(numberArr.slice(0, middleIndex), target);
  }
}

Algorithm: Binary Search @ repl.it

資料來源

• Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy