多くのデータから目的とするデータを見つけるのが探索法（Search） です。データベース等では探索は基本的な技法で，色々な方法が考えられています。ここでは探索法の内から最も基本的な方法である

逐次探索法（Sequential Search)

と

２分探索法(Binary Search)

を紹介します。

　 まず，最も素朴な方法である逐次探索法を説明します。

　この方法はデータを順次調べ，目的のデータを探すと言うものです。全く素朴な方法ですが，どのようなデータにも使え，プログラムも簡単で，データ数が余り多くない場合には適したものです。

　 文字列が何件か与えられたとき，目的とする文字列が何番目ののものであるか見つけることを考えます。

例えば，住所録で名前を与えたときその人のデータが何番目であるか求めるような問題です。

　簡単にためのアルファベットからなる10個文字列が与えられ，その中から目的とするデータの番号を見つけることにします。

　与えられた文字列が配列変数で D$(1), D$(2), ..., D$(10) と与えられたとします。

このとき，例えば，John は何番目かということです。

　逐次探索は文字通り，最初から順次目的とするデータであるか調べていく方法です。プログラムにすると次のようになります。

Key$="John"
For i=1 to 10
   if Key$=D$(i) then Exit For
Next i
Print i

　ここで，使っている Exit For は For文を脱出する命令です。

　簡単ですね。この場合は目的とするデータが一つしかないですが，２つ以上ある場合，それらをすべて求めるのであれば，次のようにすると得られます。

Key$="John"
For i=1 to 10
   if Key$=D$(i) then Print i
Next i

　これも簡単です。もし部分に含むようなデータをすべて求めると言う場合は少し複雑です。

例えば，"J" を含むすべてのデータ番号を求めると言った場合です。しかし，この場合も，Basic では InStr関数があります。これを使うと簡単に書けます。

Key$="J"
For i=1 to 10
   if InStr(1,D$(i),Key$)>0 then Print i
Next i

　この InStr関数は含まれる文字列の位置を返す関数です。この例の場合，InStr(1,D$(i),Key$)はD$(i)の最初からKey$を探し，見つかった場合，その位置を返します。見つからない場合は 0　を返します。ですから，この値が正ということは，含まれていると言うことを示します。

　逐次探索法のアイデアは以上で全てです。素朴な方法ですが色々な状況で使えることが分かると思います。

　１つ例を挙げます。次のプログラムはテキストファイルから，目的の文字列 Key$ を含む行を全て表示するものです。

Input "探すファイル名",FName$
Input "探す文字列",Key$
Open FName$ for input as #1
While not eof(1)
   Line input #1,L$
   if InStr(1,L$,Key$)>1 then Print L$
Wend
Close #1
End

　これだけのプログラムですが，場合によっては使えます。実際，１０万行のテキストファイルでも短時間で探索は終了します。

　逐次探索法はデータの数が倍になれば，探索に要する時間も大体倍になります。ですから，非常に大量のデータの中からデータを探索する場合それなりの時間が必要です。

　次に紹介する，２分探索法は扱えるデータに制限がありますが，可能な状況では非常に高速に探索を行います。

　２分探索法は，探索するデータが既に整列されていて，その各々のデータにランダムにアクセスできる場合に適用できます。　逐次探索法ではこのような制限はありませんでした。

　例えば，アルファベットからなる10個文字列D$(1), D$(2), ..., D$(10)が与えられ，その中から目的とするデータの番号を見つけることにします。２分探索法を使うためにはそれが整列されていなくてはなりません。即ち，

のような形に既にデータが順に並んでいなければなりません。更にこれらのデータにランダムにアクセスできる，即ち，データ番号を与えたとき，すぐにそのデータを読み出せる必要があります。

　今のように，配列変数にデータが格納されている場合は，何番のデータでも直ちに読み出せます。しかし，例えばテキストファイルに一列に格納されている場合，それらのデータを飛び飛びに読み出すことは出来ません。勿論，ファイルにデータを，飛び飛びに読めるような形式で格納する方法もありますが（このようなファイル形式をランダムアクセスファイルと言います。但し，Tiny Basic ではサポートされていません。），扱いが複雑です。

　整列され，ランダムアクセス可能な場合を考えます。２分探索法は私たちが，英語の辞書を引くときの様な方法で，探索を行います。

例えば，上の例で，Key$="John" が何番目か探すとします。

1. まず，中央のデータD$(5)="Kate"とKey$="John"と比較します。
2. Key$<D$(5) ですから，"John" は5番未満であることが分かります。
3. そこで，次に１と５の中間である３番のデータD$(3)="Jack"とKey$="John"と比較します。
4. D$(3)<Key$ ですから，"John" は3番より大きいことが分かります。
5. そこで，３と５の中間である４番のデータD$(4)="John"とKey$="John"と比較します。
6. 一致しましたので，これで４番であることが分かりました。

　このように，全体を半分にして，その左か右かに調べて，残りの範囲を更に半分に分け探すと言うことから，２分探索法と言われます。

　今の処理をプログラムで表してみましょう（勿論，完全なプログラムではありません。処理の部分だけです）。説明のために行番号を付けます。

01  Key$="John"
02  left=1
03  right=10
04  Do
05     c = Int((left+right)/2)
06     If Key$ >= D$(c) then
07        left =c+1
08     Else
09        right=c-1
10     End If 
11  Loop Until ((Key$=D$(c)) or left>right)
12  If Key$=D$(c) then
13     Print c
14  Else
15     Print "Data Not found"
16  End if

　４行から１１行が主要部分です。２，３行のleftとrightはデータがある場所の範囲を示します。これを狭めていって，交差したら終了です。

　５行では探索する候補をleftとrightの中央に決めています。６，７行では Key$ が D$(c) より大きい場合，候補の左端 left を c の右隣 c+1 にします。Key$=D$(c) の場合もこれに含まれますが，この場合１１行で脱出するので構いません。Key$ がD$(c) 未満の場合は，候補の右端 right を c の左隣 c-1 にします。

　この操作の結果，１１行で，Key$=D$(c) 見つかった場合で終了，left > right の場合は見つからなかった場合で終了します。それ以外の場合は，同様の操作を続けます。

　この２分探索のプログラムは再帰を使っても書くことが出来ます。再帰を使った例をBasic 入門であげました。ここで再掲します。

' ２分探索　再帰版
dim a(10000)
for i=1 to 10000
    a(i)=a(i-1)+Int(rnd*3)
next i
key=13246
Call BinSearch(A(),key,1,10000,result)
If result > 0 then
   Print result, A(result)
Else
   Print "対応データがありません"
End if
End


Sub BinSearch(A(),key,left,right,result)
   if left > right then
       result = -1
   else
      m = int((left + right)/2)
      Select case key
         Case Is < A(m)
            Call BinSearch(A(),key,left,m - 1,result)
         Case A(m)
            result = m 
         Case Is > A(m)
            Call BinSearch(A(),key,m + 1,right,result)
      End Select
   end if
End Sub 

　２分探索は扱えるデータに制限があり，全ての場合には使えませんが，使える場合非常に高速です。

実際，候補の幅が1/2づつになって行きますから，

100万件のデータでも20回程度で見つかる

ことになります。これは大変高速です。