二分搜尋法(Binary search)

介紹

Binary search又稱作二分搜尋法，是查找項目的演算法，那看到二分就知道是將要查找的項目分成兩半做搜尋，直到找到我們要找的目標。

(圖片來自於Binary Search)

不知道大家有沒有玩過猜數字遊戲，假設出題者出了一個數字56，而猜題者要從1~100之間猜數字，直到猜中為止，那當猜題者先猜46，出題者會告訴你比我的數字小，這時範圍就從1~100變成47~100，依此類推直到猜到數字。

我們可以使用二分搜尋法套用在猜數字遊戲上面，步驟為以下:

找到最大值與最小值
找到當前最大值與最小值的平均數(無條件捨去取整數)
假設平均數等於目標數，代表成功了
假設平均數小於目標值，則將最小值設為平均數加一
假設平均數大於目標值，則將最大值設為平均數減一
若無找到目標數則返回第二步驟

複雜度

時間複雜度

最好

$O(1)$

最壞

$O(logn)$

空間複雜度

迭代

$O(1)$

遞迴

$O(logn)$

實戰

可以透過leetcode 704binary-search來練習

題目說明:

給定一個排序好的陣列，找到目標數的索引位置，找不到則回傳-1。

時間複雜度必須為O(log n)

解題:

以下圖解為第一個例題

設定最左邊(left)為0，最右邊(right)為陣列數減一
找到中心位置(mid)為當前最左邊跟最右邊的平均值(向下取整數)
如果中心數字(nums[mid])跟目標數(target)相同則回傳
如果中心數字大於目標數則right等於中心位置減一
如果中心數字小於目標數則left等於中心位置加一
未找到且left小於等於right，則回到步驟2
如果right大於left，則停止：目標不存在於數組中。返回-1

迭代寫法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let mid = Math.floor((left + right) / 2);
  
  while (left <= right) {
      if (nums[mid] === target) {
        return mid;
      } else if (nums[mid] > target) {
          right = mid - 1;
      } else {
          left = mid + 1;
      }
      mid = Math.floor((left + right) / 2);
  }
  
  return -1;
};

遞迴寫法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    function search(low, high) {
        if (low > high) {
            return -1;
        }
        let mid = Math.floor((low + high) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            return search(mid + 1, high);
        } else {
            return search(low, mid - 1);
        }
    }
    return search(0, nums.length - 1);
};