二分探索法(バイナリサーチ)について
二分探索法は、探索の対象となるデータが、あらかじめ昇順または降順に整列されている場合に使うことができるアルゴリズムです。
このアルゴリズムは、次のような手順で目的の値の位置を調べていきます。
- 探索する値とデータ列の真ん中にある要素の値を比較します。
- その大小関係により、探索する値が、中央より前半または後半にあるか絞り込みます。
- 探索する値と絞り込んだデータ列の真ん中にある要素の値を比較します。
このように探索する範囲を半分ずつ狭めていくことで、目的の値がある位置を特定していきます。
データ列の後方部分でも高速に探索できるので、データ数が多い探索にはリニアサーチよりも有利です。
しかし、データ数が少ない場合や、目的の値が先頭付近にある場合は、リニアサーチのほうが速く探索できます
また、整列されていないデータの探索にはバイナリサーチは使えません。
二分探索法のイメージ
以下の図は二分探索法を使ってデータを小さい順(昇順)に並べ替える様子のイメージです。
[二分探索法のイメージ]
サンプルコード
二分探索法のアルゴリズムを以下のプログラミング言語で紹介します。
- Tcl
- Python
サンプルコードについて
各プログラミング言語の基本的な制御構造とデータ構造を使って記述しています。
必要であれば、for, foreach、リスト、配列などに書き換えたり、関数化を行って練習してください。
Tcl
[サンプル：binary-search.tcl]
#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"
# 二分探索法(binary search:バイナリサーチ)
# arr : 数値リスト
# left : 左端要素のindex
# right : 右端要素のindex
# center : 中央要素のindex
# target : 探索値
array set arr {0 11 1 13 2 24 3 26 4 35
5 37 6 46 7 49 8 54 9 68}
parray arr
puts -nonewline "探索値を入力する。: "
flush stdout
set target [gets stdin]
set left 0
set right [expr [array size arr] - 1]
while {$left <= $right} {
set center [expr ($left + $right)/2] ;# 要素の真ん中の位置
if {$arr($center) == $target} {
puts "探索値: $target は0から数えて $center 番目にあります。"
exit
} elseif {$arr($center) < $target} {
set left [expr $center + 1]
} else {
set right [expr $center - 1]
}
}
puts "探索値: $target は見つかりませんでした。"
[実行例]
$ ./binary-search.tcl arr(0) = 11 arr(1) = 13 arr(2) = 24 arr(3) = 26 arr(4) = 35 arr(5) = 37 arr(6) = 46 arr(7) = 49 arr(8) = 54 arr(9) = 68 探索値を入力する。: 54 探索値: 54 は0から数えて 8 番目にあります。 $ ./binary-search.tcl arr(0) = 11 arr(1) = 13 arr(2) = 24 arr(3) = 26 arr(4) = 35 arr(5) = 37 arr(6) = 46 arr(7) = 49 arr(8) = 54 arr(9) = 68 探索値を入力する。: 55 探索値: 55 は見つかりませんでした。
Python
[サンプル：binary-search.py]
#!/usr/bin/env python3
import sys
# 二分探索法(binary search:バイナリサーチ)
# arr : 数値リスト
# n : 要素数
# left : 左端要素のindex
# right : 右端要素のindex
# center : 中央要素のindex
# target : 探索値
arr = [11, 13, 24, 26, 35, 37, 46, 49, 54, 68]
print(arr)
target = input('探索値を入力する。: ')
target = int(target) # 文字列から数値に変換
n = len(arr)
left = 0
right = n-1
while left <= right:
center = (left + right) // 2 # 要素の真ん中の位置
if arr[center] == target:
print(f'探索値:{target} は0から数えて {center} 番目にあります。')
sys.exit()
elif arr[center] < target:
left = center + 1
else:
right = center - 1
print(f'探索値:{target} は見つかりませんでした。')
[実行例]
$ ./binary-search.py [11, 13, 24, 26, 35, 37, 46, 49, 54, 68] 探索値を入力する。: 54 探索値:54 は0から数えて 8 番目にあります。 $ ./binary-search.py [11, 13, 24, 26, 35, 37, 46, 49, 54, 68] 探索値を入力する。: 55 探索値:55 は見つかりませんでした。
コメント