4．2 番兵法
単純線形探索法では， 添え字が最大値を超えるかどうかを 監視する必要がありましたが， 配列の最後に，探索すべきキーを 入れることによって， 監視のための判定をなくす方法です。 　　　　　 しかし，探索しようとするキーが配列に入っていないときでも 例えば，７を探索しようとすると，最後で判定がＯＫになります。 　　　 ただし，番兵のところに探索しようとするキーを 入れていたわけですから， それ以前では判定が成功しなかったことが分かります。 すなわち，番兵のところでＯＫになった場合， 探索失敗とみなします。 この処理をプログラムで表現すると次のようになります。 ただし，配列はひとつだけ余分に大きくとります。 　　private int 探索(int V) //番兵法 　　{ 　　 　myArray[myArray.Length-1]=V; int i=0; 　 　　while (V != myArray[i]) i++; 　 　　return i; 　　 } 以下の線形探索と比較しみましょう。 線形探索では，１回の繰返しにおける判定が ２個あります。 　　 private int 探索(int V) 　　 { 　　　　　int R = -1;　int i = 0; 　　　　　while( i < myArray.Length) 　　　　　｛ 　　　　　　　if(V == myArray[i]) { R = i; break; } 　　　　　　　i++; 　　　　　} 　　　　　return R; 　　 } 番兵法では，繰返しにおける判定が１個になっていますので， 線形探索より，若干，効率が良いことになります。 ただし，計算量がＮに比例しているのは， 線形探索と同じです。 ［確認用プログラム例］ 　フォームは線形探索と同じ。 private int[] myArray=new int[]{2,9,7,6,5,4,3,2,-1}; private int 探索(int V) //番兵法 { 　　myArray[myArray.Length-1]=V; 　　int i=0; while (V != myArray[i]) i++; return i; } private void button1_Click(object sender, System.EventArgs e) { 　　int R = 探索(int.Parse(textBox1.Text)); 　　listBox1.SelectedIndex=R; 　　if(R==myArray.Length-1) 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]); } 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします