二分法探索

二分法探索

単純前方探索の Jiten01.java と同じデータを使います。

ファイル名 Nibun01.java

public class Nibun01 { 
    public static void main( String[] args ) {
        System.out.println( "blue".compareTo("green") );
        String[] words = { "blue", "green", "red", "white", "yellow" };
        String[] imi   = { "青", "緑", "赤", "白", "黄"};
        int i,j,m;
        i = 0;
        j = words.length-1;
        String s;
        s = javax.swing.JOptionPane.showInputDialog("検索する英単語を入れてください");
        while ( j >= i ){
            m = ( i + j )/2;
            if ( s.equals(words[m]) ){
                System.out.println( s + " の意味は " + imi[m] + " です" );
                break;
            }
            else if (s.compareTo(words[m])>0) {
                i=m+1; 
            }
            else {
                j=m-1;
            }
        }//whileの終わり
    }//mainの終わり
}//classの終わり 

コンパイルと実行は次のようにします。

$ javac Nibun01.java 
$ java Nibun01   (ダイアログがでます。redと入力したとすると)
red の意味は 赤  です
$

探す過程を表示

どうやって探したかもわかるようにしてみます。

ファイル名 Nibun02.java

public class Nibun02 { 
    public static void main( String[] args ) {
        String[] words = { "blue", "green", "red", "white", "yellow" };
        String[] imi   = { "青", "緑", "赤", "白", "黄"};
        int i,j,m;
        i = 0;
        j = words.length-1;
        String s;
        s = javax.swing.JOptionPane.showInputDialog("検索する英単語を入れてください");
        while ( j >= i ){
            m = ( i + j )/2;
            String format = "i=%2d | j=%2d | m=%2d | words[m]=%-10s\n";
            System.out.printf(format,i,j,m,words[m]);
            if ( s.equals(words[m]) ){
                System.out.println( s + " の意味は " +imi[m]+ " です" );
                break;
            }
            else if (s.compareTo(words[m])>0) {
                i=m+1; 
            }
            else {
                j=m-1;
            }
        }//whileの終わり
    }//mainの終わり
}//classの終わり

コンパイルと実行は次のようにします。

$ javac Nibun02.java 
$ java Nibun02    (ダイアログがでます。whiteと入力したとすると)
i= 0 | j= 4 | m= 2 | words[m]=red
i= 3 | j= 4 | m= 3 | words[m]=white
white の意味は 白 です

課題

1.単語が見つからない時を考慮した改良

Jiten02.java を参考に、Nibun02.javaを改良し、単語が見つからない時に「見つかりません」と報告するようにしなさい。

ファイル名 Nibun03.java

2.単語を増やす

Nibun02.javaを元に、violet 紫、brown 茶、などを追加して、正しく引けるかを確認しなさい。

ファイル名 Nibun04.java