技術系備忘録​/TypeScript​/二分探索(binary search) をテンプレートにして作成 :: シンクリッジ

開始行:
#contents JavaScript には二分探索(バイナリサーチ)が標準で用意されて... が、あれば便利だと思うので作ってみました。 -配列内にお目当ての要素があるか否かだけの関数（いわゆる C... 最初に現れた指定値以上の要素の位置を返す関数（ std::lower... 最初に現れた指定値を超えた要素の位置を返す関数（ std::upp... きっと、ありがたみ的には binary_search より lower_bound、... -単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関... -配列内に同じ値(要素)がダブって存在していても、正しくソー... もちろん、正しくソートされてない配列の場合の結果は不定で... ** コード #prettify{{ // lower_bound function lowerBound<T, U>(list: T[], value: U, less: (l: T, r: U) => boolean = (l: T, r: U) => l as any... ): 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... ): 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 an... less1: (l: U, r: T) => boolean = (l: U, r: T) => l as an... ): boolean { const first = lowerBound(list, value, less0); return first >= list.length ? false : !less1(value, list... } }} ** サンプルコード #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} :... } }} ** サンプルコード の実行結果 -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 * よもやま - お気付きの方がおられたら嬉しいのですが、本稿は以前記載... - コードは TypeScript で記述してありますが、試しに動かし...

終了行:
#contents JavaScript には二分探索(バイナリサーチ)が標準で用意されて... が、あれば便利だと思うので作ってみました。 -配列内にお目当ての要素があるか否かだけの関数（いわゆる C... 最初に現れた指定値以上の要素の位置を返す関数（ std::lower... 最初に現れた指定値を超えた要素の位置を返す関数（ std::upp... きっと、ありがたみ的には binary_search より lower_bound、... -単純な配列にしか使えないんじゃ使い勝手が悪いので、比較関... -配列内に同じ値(要素)がダブって存在していても、正しくソー... もちろん、正しくソートされてない配列の場合の結果は不定で... ** コード #prettify{{ // lower_bound function lowerBound<T, U>(list: T[], value: U, less: (l: T, r: U) => boolean = (l: T, r: U) => l as any... ): 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... ): 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 an... less1: (l: U, r: T) => boolean = (l: U, r: T) => l as an... ): boolean { const first = lowerBound(list, value, less0); return first >= list.length ? false : !less1(value, list... } }} ** サンプルコード #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} :... } }} ** サンプルコード の実行結果 -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 * よもやま - お気付きの方がおられたら嬉しいのですが、本稿は以前記載... - コードは TypeScript で記述してありますが、試しに動かし...

ページ名: