4．3 ２分探索法
２分探索（binary search）は， 配列内のキーを昇順または降順にソートしておき， 効率的に探索するアルゴリズムです。 たとえば，次のように昇順に並んだ配列の中央， ７番目と比較します。 キーがこの値より大きければ， ８番目以降をサーチすればよいことになります。 小さければ， ６番目以前をサーチすればよいことになります。 　　 キー値が７番目の値２２より大きかった場合， 次は，８番目と1４番目の中央，すなわち１１番目と比較して， 大小比較により，更に範囲を狭めます。 範囲を指定するために， 左端を示すLeft，右端を示すRightというポインタを用意すると 中央位置は， 　　 　　　PC=(Left+Right)/2 となります。ポインタの変更は， 　　�@）値が大きければLeft =PC+1 　　�A）値が小さければRight=PC-1 とします。 キー値３３を探索した場合の流れは以下のようになります。 　　 ただし，たとえば３６を探索しようとすると， 　　 表中に３６がないので，LeftとRightが逆転してしまいます。 同じように３０を探索しようとすると，同じように逆転してしまいます。 　　 このように，LeftとRightが逆転したら探索失敗とみなします。 ［確認用プログラム例］ 判定する中央値がどのように変化するかを確認するために， 逐次的に判定する処理を追加し， 中央値をリストボックスの選択状態で示します。 private int[] myArray= new int[]{4,8,20,28,30,35,40,59,65,75,95}; private int Mode;　　　　　　　　// 逐次的に処理するための変数 private int MP1, MP2, MV;　　// 逐次的に処理するための変数 private int 探索(int V) { 　　int p1 = 0; int p2 = myArray.Length - 1; int p; 　　while(p1<=p2) 　　{ 　　　　　p = (p1 + p2) / 2; 　　　　　if (myArray[p] ==V ) return p; 　　　　　else if(myArray[p] < V) p1 = p + 1; 　　　　　else p2 = p - 1; } 　　　　　return -1; } private void button1_Click(object sender, System.EventArgs e) { 　　　int R = 探索(int.Parse(textBox1.Text)); 　　　listBox1.SelectedIndex=R; 　　　if (R<0) MessageBox.Show("探索失敗"); } private void Form1_Load(object sender, System.EventArgs e) { 　　　listBox1.Items.Clear(); 　　　for(int i=0; i<myArray.Length; i++) 　　　　　　listBox1.Items.Add(myArray[i].ToString()); 　　　Mode=0; } private void button2_Click(object sender, System.EventArgs e) { 　　　int p, CV ; string Cmp, R; 　　　if (Mode == 0) 　　　{ 　　　　　MP1 = 0; MP2=myArray.Length - 1; 　　　　　MV = int.Parse(textBox1.Text); 　　　　　Mode = 1; 　　　} 　　　p　=　(MP1 + MP2)　/　2; 　　　CV　=　myArray[p]; 　　　if (CV == MV) { Cmp=" = "; R = "検索成功"; Mode = 0; } 　　　else 　　　{ 　　　　　　if(CV < MV){ Cmp = " < "; MP1 = p + 1;} 　　　　　　else　　　　　 { Cmp = " > " MP2 = p - 1;} 　　　　　　R = ””; 　　　　　　if (MP2 < MP1) { R = “検索失敗”; Mode = 0;} 　　　} 　　　label2.Text = CV.ToString() + Cmp + MV.ToString() + " " + R; 　　　listBox1.SelectedIndex = p; 　　　if(R != "") 　　　{ 　　　　　　MessageBox.Show("探索がおわりました"); 　　　　　　listBox1.SelectedIndex = -1; 　　　} } 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします