逐次探索の Chikuji01.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] です $
どうやって探したかもわかるようにしてみます。
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を忘れないように。
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; 関係と、削除された部分はわかりにくいかもしれません。
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 見つかりません $
原因がわかったら直してください。