バイナリサーチ
バイナリサーチ
問: ソートされた数値の配列と数値target
を受け取り、配列中のtarget
のインデックスを求める。その際、バイナリサーチを用いること。
アルゴリズム実装 $O(\log n)$
配列の要素数をn
としたとき、left=0
、right=n
の変数を作る。また、left
とright
の中央の位置をmid
とする。
array[mid] === target
ならtarget
が見つかったとして探索終了。left >= right
なら見つからなかったとして探索終了。array[mid] > target
ならtarget
は配列の左半分にあるので、right=mid-1
として0へarray[mid] < target
ならtarget
は配列の右半分にあるので、left=mid+1
として0へ
function binarySearch(array, target) { let left = 0 let right = array.length - 1 while (left <= right) { const mid = Math.floor((left + right) / 2) if (array[mid] > target) { right = mid - 1 } else if (array[mid] < target) { left = mid + 1 } else { return mid } } return -1 }
バイナリサーチは一回実行するごとに対象の配列の要素数が1/2になる。最悪の場合要素数が1になるまで実行されるので、計算量はその繰り返し回数をk
とすると
底数を無視して、$O(\log n)$となる