二分探索法
効率的な処理を行う代表的な手法に2分法があります。探索する広い領域があるとき、半分ずつに領域を絞りながら探索を行います。最初に、平方根を求める方法を紹介します。平方根を求める
ａ の平方根の値は、2次方程式 f(x)= x * x - a としたとき、f(x) = 0 の解になります。この解は 0 と a の間にあります。0 を left、a を right とし、この中間点を middle とします。ここで、中間点の関数の値 f(fmiddle) と 左の left の点の関数の値 f(elft) を求めます。もし、f(fmiddle) * f(elft) <0 であれば解は左半分にあります。f(x)=0 の値は両側の符号が異なるはずです。そうでなければ。右半分にあります。左半分の場合、right の値を middle に置き換えます。これで、領域の範囲が半分になります。この操作を10回繰り返すと、2の10乗は 1024 ですから、解の範囲は約 1/1000 に縮まります。
x*x-5 のグラフと解の範囲
実際にプログラムするとこんな風になります。繰り返しの停止条件を right-left<0.00001 としています。小数点5桁まで正確に求められています。
// num の平方根の値を求める
float right, left;
float middle=0.0, fmiddle, fleft;
float num=10;
left=0.0;
right=num;
while (right-left>0.00001) {
middle=(left+right)/2.0f; //中点を求める
println("left"+left + " right:"+ right+ "middle:"+ middle);
fmiddle=middle*middle-num; //中点での値を求める
fleft=left*left-num; //左の値を求める
//解の存在範囲を変更する
if ( fmiddle * fleft< 0.0) right=middle;
else left = middle;
}
println("root="+middle);
///実行結果
left0.0 right:5.0middle:2.5
left0.0 right:2.5middle:1.25
left1.25 right:2.5middle:1.875
left1.875 right:2.5middle:2.1875
left2.1875 right:2.5middle:2.34375
left2.1875 right:2.34375middle:2.265625
left2.1875 right:2.265625middle:2.2265625
left2.2265625 right:2.265625middle:2.2460938
left2.2265625 right:2.2460938middle:2.2363281
left2.2265625 right:2.2363281middle:2.2314453
left2.2314453 right:2.2363281middle:2.2338867
left2.2338867 right:2.2363281middle:2.2351074
left2.2351074 right:2.2363281middle:2.2357178
left2.2357178 right:2.2363281middle:2.236023
left2.236023 right:2.2363281middle:2.2361755
left2.236023 right:2.2361755middle:2.2360992
left2.236023 right:2.2360992middle:2.236061
left2.236061 right:2.2360992middle:2.2360802
left2.236061 right:2.2360802middle:2.2360706
root=2.2360706
データを求める
一般にたくさんのデータがあるとき、一致するデータを探すには順番に一致チェックをするしかありません。しかし、データが大きさの順に並んでいる場合、2分探索で簡単に絞り込みができます。実行例を紹介します。サイズ 1000 の配列 a[] に 0-100000 の範囲の乱数を作成し記録します。sort() でこの配列を大きさの順に並べます。乱数で探したい下図の番号を定め、2分探索メソッド bySrch( ) を呼び出します。引数 x が探したい数、a が探す配列、left right が探す範囲の指定です。bySrch() は探す数 x が配列 a[] の中にあれば、その配列の番号を返します。1000個の配列でも10回以下で、探索ができます。
//二分探索
int num=1000;
int [] a = new int[num];
int s, n;
void setup() {
randomSeed(millis());
for (int i=0;i<num;i++) a[i]=(int)random(0, 10000);
a=sort(a);
s = (int)random(0, 999);
n = bySrch(a[s], a, 0, 999);
println("s:"+ s + " n:" + n);
}
int bySrch(int x, int[] a, int left, int right)
{
int mid=0;
while (left <= right ) {
mid = (left + right) / 2; //leftとrightの中央の位置
println("l="+left+" r="+right);
//println("mid="+a[mid]+" x="+x);
if (a[mid] <= x) left = mid + 1 ;
if ( a[mid] >= x) right = mid -1;
}
if (a[mid] == x ) return mid;//見つかった
return -1;//見つからない
}
///
l=0 r=999
l=0 r=498
l=0 r=248
l=125 r=248
l=125 r=185
l=156 r=185
l=156 r=169
l=156 r=161
s:158 n:158