|
Cur: 2020-06-03 (Wed) 10:09:06 takatsuka  |
| | + | #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]] にコピペしてみて下さい。とても便利で有難いサイトです。感謝です。 |
Back to page
