JavaScriptデータ構造の取得アルゴリズムとalgorithm_javascriptスキル

データを検索するには、逐次検索と二分検索の 2 つの方法があります。順次検索は、要素がランダムに配置されたリストに対して機能します。二分検索は、並べ替えられた要素のリストに対して機能します。二分探索はより効率的ですが、並べ替えられたリスト要素のセットである必要があります。

1: 順次検索
逐次検索とは、リストの最初の要素から順番にリストの要素を1つずつ判定し、目的の結果が見つかるか、リストの最後まで目的の要素が見つからないかを判定します。

コードは次のとおりです:

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return true;
    }
  }
  return false;
}

要素の位置に一致する順次検索関数を返すこともできます。コードは次のとおりです。

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return i;
    }
  }
  return -1;
}

2: 最小値と最大値を見つける

配列内の最小値を見つけるアルゴリズムは次のとおりです:

1. 配列の最初の要素を変数に代入し、この変数を最小値として使用します。
2. 2 番目の要素から配列の走査を開始し、それを現在の最小値と比較します。
3. 現在の要素の値が現在の最小値より小さい場合は、現在の要素を新しい最小値に設定します。
4. 次の要素に移動し、ステップ 3 を繰り返します。
5. プログラム終了時にこの変数に格納されるのは最小値です。

コードは次のとおりです:

function findMin(arr) {
  var min = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

最大値を見つけるアルゴリズムは、上記の最小値と似ています。まず、配列の最初の要素を最大値に設定し、ループして配列の残りの各要素を現在の最大値と比較します。現在の要素の値が現在の最大値より大きい場合は、要素の値を最大値に割り当てます。コードは次のとおりです:

function findMax(arr) {
  var max = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
 }

3: 二分探索法。

探しているデータが順序付けされている場合、二分探索アルゴリズムは逐次探索アルゴリズムよりも効率的です。二分探索アルゴリズムの基本原理は次のとおりです:

1. 配列の最初の位置を下限 (0) に設定します。
2. 配列の最後の要素の位置を上限 (配列の長さから 1 を引いた値) に設定します。
3. 下限が上限以下の場合は、次の操作を行います:
A. 中点を (上限と下限の境界を足したもの) を 2 で割った値に設定します。
B. 中点の要素がクエリ値より小さい場合、下限を中点要素の添字に 1 を加えた値に設定します。
C. 中点の要素がクエリ値より大きい場合、上限を中点要素の添字から 1 を引いた値に設定します。
D. それ以外の場合、中間要素は検索対象のデータであり、返すことができます。

コードは次のとおりです:

// 二分查找算法
function binSearch(data,arr) {
var lowerBound = 0;
  var upperBound = arr.length - 1;
  while(lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound)/2);
    if(arr[mid] < data) {
      lowerBound = mid + 1;
    }else if(arr[mid] > data) {
      upperBound = mid - 1;
    }else {
      return mid;
    }
  }
  return -1;
}
 // 快速排序
function qSort(list) {
  if(list.length == 0) {
    return [];
  }
  // 存储小于基准值的值
  var left = [];
  // 存储大于基准值的值
  var right = [];
  var pivot = list[0];
  for(var i = 1; i < list.length; i++) {
    if(list[i] < pivot) {
      left.push(list[i]);
    }else {
      right.push(list[i])
    }
  }
  return qSort(left).concat(pivot,qSort(right));
}
 // 测试代码
var numbers = [0,9,1,8,7,6,2,3,5,4];
var list = qSort(numbers);
console.log(binSearch(6,list));

4: 繰り返しの数を計算します。
二分探索アルゴリズムの binSearch() 関数が特定の値を見つけたとき、データセット内に他の同じ値がある場合、関数は類似した値の近くに配置されます。つまり、他の同じ値が存在する可能性があります。見つかった値の左側または右側が表示されます。

最も簡単な解決策は、2 つのループを作成することです。1 つはデータ セットを下方向または左方向に同時に走査して繰り返し回数をカウントし、次に上方向または右方向に走査して繰り返し回数をカウントします。コードは次のとおりです:

// 计算重复次数
function count(data,arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data,arr);
  if(position > -1) {
    ++count;
    arrs.push({"index":count});
    for(var i = position -1; i > 0; --i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
    for(var i = position + 1; i < arr.length; ++i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
  }
  return arrs;
}
 // 测试重复次数的代码
var arr = [0,1,1,1,2,3,4,5,6,7,8,9];
var arrs = count(1,arr);
console.log(arrs);
console.log(arrs.length);

以下に示すように: