JS二分探索アルゴリズムとコードについて共有する-jsチュートリアル-php.cn

JS二分探索アルゴリズムとコードについて共有する

零到壹度

リリース： 2018-03-20 11:20:52

オリジナル

1580 人が閲覧しました

この記事では主に JS バイナリ検索アルゴリズムとコードを共有します。必要な方は参考にしていただければ幸いです。

4.1 二分探索
アルゴリズムの紹介
二分探索は、半探索とも呼ばれ、順序付けされた配列内の特定の要素を見つけるための検索アルゴリズムです。検索プロセスは次のステップに分けることができます:
(1) まず、順序付けられた配列の中央の要素から検索を開始します。その要素がターゲット要素 (つまり、検索対象の要素) である場合、検索は実行されます。プロセスが終了するか、そうでない場合は次のステップに進みます。
(2) 対象の要素が中央の要素より大きいか小さい場合は、中央の要素より大きいか小さい配列の半分を検索し、最初の手順を繰り返します。
(3) あるステップの配列が空の場合は、目的の要素が見つからないことを意味します。
リファレンスコード:
非再帰アルゴリズム

function binary_search(arr,key){
  var low=0,
  high=arr.length-1;
  while(low<=high){
     var mid=parseInt((high+low)/2);
     if(key==arr[mid]){
        return mid;
     }else if(key>arr[mid]){
        low=mid+1;
     }else if(key<arr[mid]){
        high=mid-1;
    }else{
      return -1;
    }
  }
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,10);
alert(result); //  9 返回目标元素的索引值

ログイン後にコピー

再帰アルゴリズム

function binary_search(arr,low,high,key){
  if(low>high){
    return -1;   
  }
  var mid=parseInt((high+low)/2);
  if(arr[mid]==key){
    return mid;
  }else if(arr[mid]>key){
    high=mid-1;
    return binary_search(arr,low,high,key);
  }else if(arr[mid]<key){
    low=mid+1;
    return binary_search(arr,low,high,key);
  }
};
var arr=[1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result=binary_search(arr,0,13,10);
alert(result); // 9 返回目标元素的索引值

ログイン後にコピー

以上がJS二分探索アルゴリズムとコードについて共有するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。