JS數組搜尋之折半搜尋的實作方法詳解

這篇文章主要介紹了JS陣列搜尋之折半搜尋實作方法,結合具體實例形式分析了javascript數組折半搜尋演算法的原理、實作技巧與相關注意事項,需要的朋友可以參考下

本文實例講述了JS數組搜尋之折半搜尋實作方法。分享給大家供大家參考，具體如下：

一. 方法原理：

當從一個給定的序列數組arr中, 查找某個特定值value時, 折半搜尋法是這樣做的:

1. 確定搜尋範圍的起始點: 起點startIndex = 0, 終點endIndex = arr.length - 1;

2. 根據起始點來確定一個中間點middle = Math.floor((終點- 起點) / 2);

#3. 在startIndex a09a6726fa309d8dcbfa1b2471663cf5 value

調整搜尋範圍為陣列的前半部, 即startIndex = 0, endIndex = middle - 1;

#接著, 重新計算middle, 再比較arr[middle]與value, 直到兩者相等或startIndex >= endIndex.

二. 程式碼：

// 该例的写法适用于序列为由小到大的数组
function binarySearch(arr, value) {
  var startIndex = 0,
  endIndex = arr.length - 1;
  middle = Math.floor((endIndex - startIndex) / 2);
  while (arr[middle] !== value && startIndex < endIndex) {
    if (arr[middle] > value) {
      endIndex = middle - 1;
    } else if (arr[middle] < value) {
      startIndex = middle + 1;
    }
    middle = Math.floor((endIndex - startIndex) / 2);
  }
  return (arr[middle] !== value) ? -1 : middle;
}

#三. 優缺點：

(1) 優點:

每查找一次, 被尋找的陣列項數會減少一半, 因此其在效能上要優於線性搜尋法(在陣列項目較多時, 尤其明顯);

(2) 缺點:

只適用於序列數組, 在對普通數組使用該方法之前, 需要對數組進行排序

以上是JS數組搜尋之折半搜尋的實作方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！