JavaScript には二分探索(バイナリサーチ)が標準で用意されてません。たぶん。
が、あれば便利だと思うので作ってみました。
// 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]); }
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}`); }
-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
(This host) = https://thinkridge.com