二分探索

二分探索

逐次探索の Chikuji01.java と同じデータを使います。

ファイル名 Nibun01.java

public class Nibun01 { 
    public static void main( String[] args ) {
        int[] data = { 11, 24, 36, 42, 58, 63, 77 };
        int i,j,m;
        i = 0;
        j = data.length-1;
        while ( j >= i ){
            m = (i+j)/2;
            if ( data[m] == 36 ){
                System.out.println( "発見 data["+m+"] です" );
                break;
            }
            else if (data[m]>36) {
                j=m-1;
            }
            else {
                i=m+1; 
            }
        }//whileの終わり
    }//mainの終わり
}//classの終わり

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

$ javac Nibun01.java 
$ java Nibun01 
発見 data[2] です
$

探す過程を表示

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

ファイル名 Nibun02.java

public class Nibun02 { 
    public static void main( String[] args ) {
        int[] data = { 11, 24, 36, 42, 58, 63, 77 };
        int i,j,m;
        i = 0;
        j = data.length-1;
        while ( j >= i ){
            m = (i+j)/2;
            String format = "i=%2d | j=%2d | m=%2d | data[m]=%3d\n";
            System.out.printf(format,i,j,m,data[m]);
            if ( data[m] == 36 ){
                System.out.println( "発見 data["+m+"] です" );
                break;
            }
            else if (data[m]>36) {
                j=m-1;
            }
            else {
                i=m+1; 
            }
        }//whileの終わり
    }//mainの終わり
}//classの終わり

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

$ javac Nibun02.java 
$ java Nibun02 
i= 0 | j= 6 | m= 3 | data[m]= 42
i= 0 | j= 2 | m= 1 | data[m]= 24
i= 2 | j= 2 | m= 2 | data[m]= 36
発見 data[2] です

探索する値を後で入力します

まえにも使ったJOptionPane.showInputDialog()を用いて36以外の数も探せるようにします。importを忘れないように。

ファイル名 Nibun03.java

import javax.swing.*;

public class Nibun03 { 
    public static void main( String[] args ) {
        int[] data = { 11, 24, 36, 42, 58, 63, 77 };
        int n;
        String s;
        s = JOptionPane.showInputDialog("検索する整数を入れてください?");
        n = Integer.parseInt(s);
        int i,j,m;
        i = 0;
        j = data.length-1;
        while ( j >= i ){
            m = (i+j)/2;
            String format = "i=%2d | j=%2d | m=%2d | data[m]=%3d\n";
            System.out.printf(format,i,j,m,data[m]);
            if ( data[m] == n ){
                System.out.println( "発見 data["+m+"] です" );
                break;
            }
            else if (data[m]>n) {
                j=m-1;
            }
            else {
                i=m+1; 
            }
        }//whileの終わり
    }//mainの終わり
}//classの終わり

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

$ javac Nibun03.java
$ java Nibun03  (ダイアログがでます。58と入力したとすると)
i= 0 | j= 6 | m= 3 | data[m]= 42
i= 4 | j= 6 | m= 5 | data[m]= 63
i= 4 | j= 4 | m= 4 | data[m]= 58
発見 data[4] です
$ 

見つからないときはどうなるでしょうか。

$ javac Nibun03.java
$ java Nibun03  (ダイアログがでます。55と入力したとすると)
i= 0 | j= 6 | m= 3 | data[m]= 42
i= 4 | j= 6 | m= 5 | data[m]= 63
i= 4 | j= 4 | m= 4 | data[m]= 58
$ 

英和辞典を作る

英和辞典も二分探索にします。まず、5つぐらいで試してみます。

前半(配列の用意)は、Jiten02.java に対して変わるところをこの色で示しました。

後半(探索部分)は、Nibun03.java に対して変わるところをこの色で示しました。

boolean atta=false; 関係と、削除された部分はわかりにくいかもしれません。

ファイル名 Jiten03.java

import javax.swing.*;

public class Jiten03 { 
    public static void main( String[] args ) {
        String[] word = { "blue", "green", "red", "yellow", "white" };
        String[] imi  = { "青", "緑", "赤", "黄", "白" };
        String s;
        s = JOptionPane.showInputDialog("検索する英単語を入れてください?");
        //探すものが数値でないので n=...の部分はいらなくなります。
        boolean atta=false;
        int i,j,m;
        i = 0;
        j = word.length-1;
        while ( j >= i ){
            m = (i+j)/2;
            String format = "i=%2d | j=%2d | m=%2d | word[m]=%-7s\n";
            System.out.printf(format,i,j,m,word[m]);
            if ( word[m].equals(s) ){
                System.out.println( "発見 word["+m+"] です。");
                System.out.println( word[m]+" の意味は「"+imi[m]+"」です。" );
                atta=true;
                break;
            }
            else if (word[m].compareTo(s)>0) {
                j=m-1;
            }
            else {
                i=m+1; 
              }
        }//whileの終わり
        if ( atta==false ) System.out.println( "見つかりません" );
    }//mainの終わり
}//classの終わり

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

$ javac Jiten03.java
$ java Jiten03  (ダイアログがでます。greenと入力したとすると)
i= 0 | j= 4 | m= 2 | word[m]=red    
i= 0 | j= 1 | m= 0 | word[m]=blue   
i= 1 | j= 1 | m= 1 | word[m]=green  
発見 word[1] です。
green の意味は「緑」です。
$ 

Stringが等しいかどうかは == でなく、.equals() を使いましたが、比較は .compareTo() を使います。

失敗しました。whiteを引くことができません。なぜだかわかりますか。

$ javac Jiten03.java
$ java Jiten03  (ダイアログがでます。whiteと入力すると)
i= 0 | j= 4 | m= 2 | word[m]=red    
i= 3 | j= 4 | m= 3 | word[m]=yellow 
見つかりません
$ 

原因がわかったら直してください。