[[428826]]

本文轉載自微信公眾號「JS每日一題」，作者灰灰。轉載本文請聯(lián)系JS每日一題眾號。

一、是什么

在計算機科學中，二分查找算法，也稱折半搜索算法，是一種在有序數(shù)組中查找某一特定元素的搜索算法

想要應用二分查找法，則這一堆數(shù)應有如下特性：

• 存儲在數(shù)組中
• 有序排序

搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束

如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較

如果在某一步驟數(shù)組為空，則代表找不到

這種搜索算法每一次比較都使搜索范圍縮小一半

如下圖所示：

相比普通的順序查找，除了數(shù)據(jù)量很少的情況下，二分查找會比順序查找更快，區(qū)別如下所示：

二、如何實現(xiàn)

基于二分查找的實現(xiàn)，如果數(shù)據(jù)是有序的，并且不存在重復項，實現(xiàn)代碼如下：

function BinarySearch(arr, target) { 
    if (arr.length <= 1) return -1 
    // 低位下標 
    let lowIndex = 0 
    // 高位下標 
    let highIndex = arr.length - 1 
 
    while (lowIndex <= highIndex) { 
        // 中間下標 
        const midIndex = Math.floor((lowIndex + highIndex) / 2) 
        if (target < arr[midIndex]) { 
            highIndex = midIndex - 1 
        } else if (target > arr[midIndex]) { 
            lowIndex = midIndex + 1 
        } else { 
            // target === arr[midIndex] 
            return midIndex 
        } 
    } 
    return -1 
} 

如果數(shù)組中存在重復項，而我們需要找出第一個制定的值，實現(xiàn)則如下：

function BinarySearchFirst(arr, target) { 
    if (arr.length <= 1) return -1 
    // 低位下標 
    let lowIndex = 0 
    // 高位下標 
    let highIndex = arr.length - 1 
 
    while (lowIndex <= highIndex) { 
        // 中間下標 
        const midIndex = Math.floor((lowIndex + highIndex) / 2) 
        if (target < arr[midIndex]) { 
            highIndex = midIndex - 1 
        } else if (target > arr[midIndex]) { 
            lowIndex = midIndex + 1 
        } else { 
            // 當 target 與 arr[midIndex] 相等的時候，如果 midIndex 為0或者前一個數(shù)比 target 小那么就找到了第一個等于給定值的元素，直接返回 
            if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex 
            // 否則高位下標為中間下標減1，繼續(xù)查找 
            highIndex = midIndex - 1 
        } 
    } 
    return -1 
} 

實際上，除了有序的數(shù)組可以使用，還有一種特殊的數(shù)組可以應用，那就是輪轉后的有序數(shù)組

有序數(shù)組即一個有序數(shù)字以某一個數(shù)為軸，將其之前的所有數(shù)都輪轉到數(shù)組的末尾所得

例如，[4, 5, 6, 7, 0, 1, 2]就是一個輪轉后的有序數(shù)組

該數(shù)組的特性是存在一個分界點用來分界兩個有序數(shù)組，如下：

分界點有如下特性：

• 分界點元素 >= 第一個元素
• 分界點元素 < 第一個元素

代碼實現(xiàn)如下：

function search (nums, target) { 
  // 如果為空或者是空數(shù)組的情況 
  if (nums == null || !nums.length) { 
    return -1; 
  } 
  // 搜索區(qū)間是前閉后閉 
  let begin = 0, 
    end = nums.length - 1; 
  while (begin <= end) { 
    // 下面這樣寫是考慮大數(shù)情況下避免溢出 
    let mid = begin + ((end - begin) >> 1); 
    if (nums[mid] == target) { 
      return mid; 
    } 
    // 如果左邊是有序的 
    if (nums[begin] <= nums[mid]) { 
      //同時target在[ nums[begin],nums[mid] ]中，那么就在這段有序區(qū)間查找 
      if (nums[begin] <= target && target <= nums[mid]) { 
        end = mid - 1; 
      } else { 
        //否則去反方向查找 
        begin = mid + 1; 
      } 
      //如果右側是有序的 
    } else { 
      //同時target在[ nums[mid],nums[end] ]中，那么就在這段有序區(qū)間查找 
      if (nums[mid] <= target && target <= nums[end]) { 
        begin = mid + 1; 
      } else { 
        end = mid - 1; 
      } 
    } 
  } 
  return -1; 
}; 

對比普通的二分查找法，為了確定目標數(shù)會落在二分后的哪個部分，我們需要更多的判定條件

三、應用場景

二分查找法的O(logn)讓它成為十分高效的算法。不過它的缺陷卻也是比較明顯，就在它的限定之上：

有序：我們很難保證我們的數(shù)組都是有序的

數(shù)組：數(shù)組讀取效率是O(1)，可是它的插入和刪除某個元素的效率卻是O(n)，并且數(shù)組的存儲是需要連續(xù)的內(nèi)存空間，不適合大數(shù)據(jù)的情況

關于二分查找的應用場景，主要如下：

不適合數(shù)據(jù)量太小的數(shù)列;數(shù)列太小，直接順序遍歷說不定更快，也更簡單

每次元素與元素的比較是比較耗時的，這個比較操作耗時占整個遍歷算法時間的大部分，那么使用二分查找就能有效減少元素比較的次數(shù)

不適合數(shù)據(jù)量太大的數(shù)列，二分查找作用的數(shù)據(jù)結構是順序表，也就是數(shù)組，數(shù)組是需要連續(xù)的內(nèi)存空間的，系統(tǒng)并不一定有這么大的連續(xù)內(nèi)存空間可以使用

參考文獻

https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95#javascript_%E7%89%88%E6%9C%AC

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html