アルゴリズム（バイナリサーチ）

さて今回はサーチプログラムにおける代表的アルゴリズムのバイナリサーチについて説明します。

バイナリサーチとは
フローチャートを書く
プログラムを書く
1. Scratchで書く
2. Pythonで書く
まとめ

バイナリサーチとは

バイナリサーチとはサーチプログラムの一種です。

サーチプログラム（探索プログラム）については、前回、リニアサーチについて説明しました。リニアサーチについては、配列の最初から順番に探す数があるか調べていくというやり方で、アルゴリズムはシンプルでわかりやすいのですが、探す数が配列の最初のほうにあったらよいのですが、逆に配列の最後の方にあったら時間がかかってしまうという欠点もありました。

詳しくはこちら

アルゴリズム（リニアサーチ）

今回はアルゴリズムの中におけるリニアサーチについて述べたいと思います。なお、この記事を書いた後、もっとよいプログラムの書き方を見つけて追加記事を書いています。こちらサーチプログラムとはサーチプログラムとは、その名のと...

これに対して、バイナリサーチは二分探索とも呼ばれており、その名のとおり調べる対象を半分に分割しながら探していきます。そのため、アルゴリズムとしては少し難しくなるのですが、より効率的に目的とする数を探すことができます。

ただし、このバイナリサーチは、調べる対象データがあらかじめ小さい数から順番に整列されている必要があります。またその為、大小を比較できるものでしか探索できません。単純に言えば数字の探索ですが、文字の場合、文字コードで大小が判別できる場合は探索対象となります。

おい、その数の整列ってどうやるんだよって話ですよね。それは、またソートプログラムのところで後日説明したいと思います。（そう考えると、サーチよりもソートの方を先に書くべきだったかなとも思うのですが、ソートプログラムは種類が多いので、まずはサーチから説明をはじめちゃいました。）

さてバイナリサーチのイメージはこちらです。

このバイナリサーチですが、配列の中心をもとめ、その配列の中心に入っている数字と探す数を比較して、探す数の方が小さければ、その後は左側を探索、探す数が大きければ右側を探索ということを繰り返すやりかたになります。

ちなみに真ん中の数の探し方は、配列の一番左の値と配列の一番右の値の和を２で割って、小数点以下を切り捨てするやり方が一般的だと思います。

フローチャートを書く

さて、原理がわかったところでバイナリサーチのフローチャートを書いてみます。

バイナリサーチのフローですが、変数として探す数 s 、探す対象の数を配列 A [ ]に準備。結果を格納する変数としてresultを用意します。

そして、配列の左端を決める為に変数Lに初期値 0 を代入。配列の右端を決めるために配列Rに初期値として配列の長さ-1を入れます。

配列の真ん中を示す変数として i を用意。この真ん中を求めるのが、先に話したとおり（L＋R）/２の計算をして小数点以下を切り捨てます。その結果、i は配列の真ん中を示すため探す数s と A[i]を比較します。

もしs = A[ i ] なら探す数が見つかったのでresultにA[ i ]の値をいれて、探索終了。 s < A[ i ]であれば、探す数は真ん中より左にあるため、次の真ん中の数を探すためにRの値をi-1にします。逆に s > A[ i ] であれば、探す数は真ん中より右にあるため、次の真ん中の数を探すためにLをi+1にします。

この処理をL ≦ R である限り、言い換えるとL > R になるまで繰り返すという処理になります。

プログラムを書く

次はいつものようにScratchとPythonでプログラムを書いてみますね。

Scratchで書く

Scratchで書いたプログラムがこちら

Scratchサイトでの共有はこちらです。

https://scratch.mit.edu/projects/339635047/

さて解説します。プログラムについてはフローの流れでScratchの場合はどうもブロックの作り上、フローチャートとは完全に一致しないのですが、基本の流れはフローチャートと同じです。違う点としたら、Scratchの場合は配列の一番目は１と表現されるので、配列の位置が0からではなく1から始めるため、フローチャートとは１つずれるという点です。また配列の真ん中を計算する過程においては小数点以下を切り捨てるためL+R/２の結果に対して切り下げを施しています。

またこのプログラムでは何度も試せるようにスペースキーを押したら主要な変数が0になるようにしています。

Pythonで書く

さて次はPythonです。

<span style="font-size: 16px;">print("探す正の数は何？")
s = int(input())
A = [1,2,3,6,9,12,15,18,22]
i = 0
L = 0
result = -1
R = len(A)-1
while L &lt;= R:
i = int((L+R)/2)
if s == A[i]:
result = A[i]
print("探す数"+str(s)+"は配列Aの"+str(i+1)+"番目にあったよ")
break
elif s &lt; A[i]:
R = i-1
else:
L = i+1
if s != result:
print("探す数"+str(s)+"はみつからなかったよ")</span>

<spanstyle="font-size: 16px;">print("探す正の数は何？")

s=int(input())

A=[1,2,3,6,9,12,15,18,22]

i=0

L=0

result=-1

R=len(A)-1

whileL<=R:

i=int((L+R)/2)

ifs==A[i]:

result=A[i]

print("探す数"+str(s)+"は配列Aの"+str(i+1)+"番目にあったよ")

break

elifs<A[i]:

R=i-1

else:

L=i+1

ifs!=result:

print("探す数"+str(s)+"はみつからなかったよ")</span>

で、書いてみましたが、正直、フローチャートどおりには作れませんでした。結局、うまく処理するためにはresultの初期値をきめて、最後にif文で見つける数とresultの結果が一致しない場合、見つからない場合の条件を追加しています。おそらくこれはWhileの条件設定がPythonとScratchで表現の仕方が違うからかなと思っています。