メニュー
ブログ更新履歴
コンテンツ更新履歴
リンク
  • rlib-MML デモページ
  • MML (Music Macro Language) をコンパイルし、再生や標準MIDIファイル出力をブラウザ上で行える形にまとめています。
  • Magome
  • クラウドベースのMIDIシーケンサ
    音楽制作に興味のある方を対象に、スタンドアロンでも使え、ネットならではの面白さも兼ね備えた音楽制作アプリの提供を目指しています。
twitter
  
Cur: 2020-06-03 (Wed) 10:09:06 takatsuka source
Line 1: Line 1:
 +#contents
 +JavaScript には二分探索(バイナリサーチ)が標準で用意されてません。たぶん。
 +が、あれば便利だと思うので作ってみました。
 +-配列内にお目当ての要素があるか否かだけの関数(いわゆる C++ で言う std::binary_search )だけでなく、
 +最初に現れた指定値以上の要素の位置を返す関数( std::lower_bound )と、
 +最初に現れた指定値を超えた要素の位置を返す関数( std::upper_bound )を用意してます。
 +きっと、ありがたみ的には binary_search より lower_bound、upper_bound の方が上だろうなと思います。
 +
 +-単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関数を渡せるようにして、どんな形の配列でも対応できるようにしてあります。
 +
 +-配列内に同じ値(要素)がダブって存在していても、正しくソートされている配列であれば正常に動作します。
 +もちろん、正しくソートされてない配列の場合の結果は不定です。
 +
 +** コード [#x0a2403a]
 +#prettify{{
 +// lower_bound
 +function lowerBound<T, U>(list: T[], value: U,
 +    less: (l: T, r: U) => boolean = (l: T, r: U) => l as any < r
 +): number {
 +    let count = list.length;
 +    let first = 0;
 +    while (0 < count) {
 +     const count2 = count / 2 | 0;
 +     const mid = first + count2;
 +     if (less(list[mid], value)) {
 +     first = mid + 1;
 +     count -= count2 + 1;
 +     } else {
 +     count = count2;
 +     }
 +    }
 +    return first;
 +}
 +
 +// upper_bound
 +function upperBound<T, U>(list: T[], value: U,
 +    less: (l: U, r: T) => boolean = (l: U, r: T) => l as any < r
 +): number {
 +    return lowerBound(list,value,(l,r)=>!less(r,l));
 +}
 +
 +// binary_search
 +// ・2つの比較関数というのがいささか冗長な気がしています。もう少しスマートな書き方がもしあれば教えてほしいです
 +function binarySearch<T, U>(list: T[], value: U,
 +    less0: (l: T, r: U) => boolean = (l: T, r: U) => l as any < r,
 +    less1: (l: U, r: T) => boolean = (l: U, r: T) => l as any < r
 +): boolean {
 +    const first = lowerBound(list, value, less0);
 +    return first >= list.length ? false : !less1(value, list[first]);
 +}
 +
 +}}
 +
 +** サンプルコード [#lc2cf439]
 +#prettify{{
 +const sortedList = [-5, 0, 5, 10, 10, 11, 11, 13, 18];      // ソート済みの配列
 +const testValues = [-7, -5, 0, 1, 2, 10, 12, 13, 18, 19];  // テストケース
 +
 +for (const v of testValues) {
 +    const l = lowerBound(sortedList, v);
 +    const u = upperBound(sortedList, v);
 +    const b = binarySearch(sortedList, v);
 +    console.log(`${v} -> lowerBound=${l} : upperBound=${u} : binarySearch=${b}`);
 +}
 +}}
 +
 +** サンプルコード の実行結果 [#k9dd6a18]
 + -7 -> lowerBound=0 : upperBound=0 : binarySearch=false
 + -5 -> lowerBound=0 : upperBound=1 : binarySearch=true
 + 0 -> lowerBound=1 : upperBound=2 : binarySearch=true
 + 1 -> lowerBound=2 : upperBound=2 : binarySearch=false
 + 2 -> lowerBound=2 : upperBound=2 : binarySearch=false
 + 10 -> lowerBound=3 : upperBound=5 : binarySearch=true
 + 12 -> lowerBound=7 : upperBound=7 : binarySearch=false
 + 13 -> lowerBound=7 : upperBound=8 : binarySearch=true
 + 18 -> lowerBound=8 : upperBound=9 : binarySearch=true
 + 19 -> lowerBound=9 : upperBound=9 : binarySearch=false
 +
 +
 +* よもやま [#h8e0186b]
 +- お気付きの方がおられたら嬉しいのですが、本稿は以前記載した [[技術系備忘録/PHP/二分探索(binary search)]] とほぼ同じです。なお、サンプルコード(テストケース)もまったく同じなのは手を抜いたとかではなく比較しやすいかなと考えた次第です。
 +
 +- コードは TypeScript で記述してありますが、試しに動かしたいとか、素の JavaScript のコードが欲しいとかの場合は、[[こちらのサイト(TypeScript Playground)>https://www.typescriptlang.org/play/index.html]] にコピペしてみて下さい。とても便利で有難いサイトです。感謝です。
  

  • Backup diff of 技術系備忘録/TypeScript/二分探索(binary search)(No. All)

Front page   Diff Backup Copy Rename ReloadPrint View   New Page Page list Search Recent changes   Help   RSS of recent changes (RSS 1.0) RSS of recent changes (RSS 2.0) RSS of recent changes (RSS Atom) Powered by xpWiki
Counter: 3553, today: 3, yesterday: 2