
JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2020-05-245 min read
目次
概要
JavaScriptで2分探索(バイナリサーチ)を実装してみました。
2分探索について
探索する範囲を半分に絞る→次の探索でさらに半分に絞る...という具合に探索する方法です。
前提として探索する配列などのデータがソートされている必要があります。
また、wikipediaではこのように説明されています。
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量はO(log _{2}n)である(O記法)。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度(奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個)の要素を無視することができる。
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2
より
ソース
2分探索ソースがこちらです。
関数 binarySearch
は、探索する配列と探索対象を受け取り結果のインデックスを返します。見つからなかったら-1を返します。
このサンプルでは検索結果のインデックスとともに探索時の最後に絞った探索範囲の最小値と最大値を返しています。
/**
* 2分探索
* @param Array arr ソート済みの探索対象配列
* @param Int target 探索する値
* @return Array 探索結果の添字 見つからなかった場合は-1を返す
*/
function binarySearch(arr, target) {
let idx = -1;
let iMin = 0;
let iMax = arr.length - 1;
while (iMin <= iMax) {
let iMid = Math.floor((iMin + iMax) / 2);
if (arr[iMid] === target) {
idx = iMid;
break;
} else if (arr[iMid] < target) {
iMin = iMid + 1;
} else {
iMax = iMid - 1;
}
}
return [idx, iMin, iMax]
}
//
// sample
//
let data = [0,9,1,8,2,7,3,6,4,5,10].sort((a,b) => a-b)
console.log(data)
// 0,1,2,3,4,5,6,7,8,9,10
let [idx, iMin, iMax] = binarySearch(data, 4)
console.log([idx, iMin, iMax])
// 4,4,4
参考
Recommends
JavaScriptで優先度付きキューを実装する
2021-08-01
next_permutationをJSで実装する
2021-07-22
10進数から2進数 2進数から10進数への変換 JavaScript
2020-07-12
JavaScriptの配列ショートハンド (AtCoder用)
2020-07-05
JavaScriptでワーシャルフロイド法を実装
2020-06-21
JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2020-05-24
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-13
順列・組み合わせ のサンプルコード JS [permutation] [combina...
2019-06-30
JavaScript で bit全探索
2019-06-10
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
複数キーでソートするサンプルコード JavaScript
2018-11-05
javascriptで累積和を解く
2022-02-27
JSで動的計画法を利用して部分和問題を解く
2022-02-20
JSで32ビット符号付き整数に対してのビット演算でハマった
2021-02-17
JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
2021-02-16
New Posts
[AWS CDK]ECS FargateでNestJSで作成したRESTfull APIデ...
2022-05-24
[AWS CDK]S3 CloudFront OAI Route53 構成 で NextJ...
2022-05-23
[CDK]SNS+SQS+DynamoDBでBounceとComplaint情報を収集する...
2022-04-11
[AmazonSES] node.js と ejs を利用してEメールを送信する
2022-04-09
GatsbyからNext.jsへのサイト移行
2022-04-04
[AWS CDK] Lambda で S3 オブジェクトを読み書きするStackの構築
2022-03-18
[AWS CDK] S3 + CloudFrontの構築とOriginAccessIden...
2022-03-09
[AWS CDK] Bastion(踏み台)構築。SSMとEC2InstanceConne...
2022-03-06
[AWS CDK] Cognito を構築
2022-03-04
AWS CDK v2 でVPC上にAPI Gateway + Lambda + RDS +...
2022-02-28
javascriptで累積和を解く
2022-02-27
AWS Amplify で monorepo を導入し 単一リポジトリで複数プロジェクトを...
2022-02-25
AWS CDK v2 で Lambda関数のデプロイ
2022-02-23
NextJSでDevToysのようなものを作成した
2022-02-22
JSで動的計画法を利用して部分和問題を解く
2022-02-20
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
OpenCVのMatのタイプ一覧表
2018-11-25
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
Macでターミナルからポートスキャンを行う方法。
2018-12-09
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
Date
▶︎
2022 年 (23)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
Author