JS配列検索における半検索の実装方法を詳しく解説

この記事では主に JSarraysearch の原理、実装スキル、および関連する Notes を具体的な例に基づいて紹介します。次に

この記事の例では、JS配列検索における半探索の実装方法を説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

1. メソッドの原理:

指定されたシーケンス配列 arr から特定の値を検索する場合、半分の検索メソッドは次のことを行います:

1.検索範囲の開始点を決定します: 開始点 startIndex = 0、終了点 endIndex = arr.length - 1;

2. 開始点 middle = Math.floor((終了点 - 開始点) に基づいて中間点を決定します。 ) / 2);

3. startIndex < endIndex の前提で、arr[middle] と value のサイズを比較します:

(1) arr[middle]

配列の半分、つまり、startIndex = middle + 1、endIndex = arr.length -1;

(2) arr[middle] > value

検索範囲を配列の前半に調整します。 、startIndex = 0、endIndex = middle - 1;

次に、middle を再計算し、arr[middle] と value が等しくなるか、startIndex >= endIndex になるまで比較します。

II コード:

// 该例的写法适用于序列为由小到大的数组
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;
}

III. 利点と欠点:

(1) 利点:

各検索では、検索される配列項目の数が半分に減るため、線形検索方法よりもパフォーマンスが向上します (特に配列が多い場合に顕著です) items);

(2) 欠点:

シーケンス配列にのみ適用可能、このメソッドを通常の 配列で使用する前に、配列をソートする必要があります

以上がJS配列検索における半検索の実装方法を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。