0

Java でバイナリ検索を実装しようとしていますが、コードに問題があります。探している要素が配列に存在する場合に機能します。そうでない場合、プログラムはエラー メッセージを出力しません。ここで言いたいのは -

コードを実行すると-これが出力です-

Please enter array size
2
Please enter element 0
3
Please enter element 1
4
Sorted array elements[3, 4]


Please enter the element you want to find in the array
3
Match 3 found at index 0

ただし、配列に存在しない要素を探すと、プログラムはelseループに入らず、エラーメッセージを出力します-代わりにこれを行います-

Please enter array size
2
Please enter element 0
3
Please enter element 1
4
Sorted array elements[3, 4]


Please enter the element you want to find in the array
2
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at arraysPract.BinarySearch.findElement(BinarySearch.java:82)
    at arraysPract.BinarySearch.main(BinarySearch.java:54)

ここにコードがあります - 

package arrays;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BinarySearch {
    static int[] binaryArr = null;

    public static void main(String[] args) {
        BufferedReader br = null;
        String size = "";

        try {
            System.out.println("Please enter array size");
            br = new BufferedReader(new InputStreamReader(System.in));
            size = br.readLine();
            if (size == null) {
                System.out.println("Size can't be null");
                return;
            }
            int ipSize = Integer.parseInt(size);
            binaryArr = new int[ipSize];
            String entry = "";
            for (int i = 0; i < ipSize; i++) {
                System.out.println("Please enter element " + i);
                entry = br.readLine();
                if (entry == null) {
                    System.out.println("Value can't be null");
                    return;
                }
                int arrEntry = Integer.parseInt(entry);
                binaryArr[i] = arrEntry;
            }

            Arrays.sort(binaryArr);
            System.out.println("Sorted array elements"  + Arrays.toString(binaryArr));
            System.out.println("\n");

            System.out.println("Please enter the element you want to find in the array");
            String findArrayElement = br.readLine();
            int find = Integer.parseInt(findArrayElement);      
            boolean elementExists = Arrays.asList(binaryArr).contains(find);            
            if (elementExists==false) {             
                findElement(binaryArr, find);
            }

            else {
                System.out.println("Element does not exist. Please try again");
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static int findElement(int[] test, int keyElement) {
        boolean flag = true;
        int i = 0;
        for (i = test.length / 2; i >= 0 && i < test.length;) {
            if (keyElement == test[i]) {
                flag = false;
                break;
            } else if (keyElement > test[i]) {
                i++;
                if (keyElement == test[i]) {
                    flag = false;
                } else {
                    flag = true;
                }
            } else if (keyElement < test[i]) {
                i--;
                if (keyElement == test[i]) {
                    flag = false;
                } else {
                    flag = true;
                }
            }
        }

        if (flag == false) {
            System.out.println("Match " + keyElement + " found at index " + i);
        }
        return i;
    }
}

明らかなエラーを見落としている場合は、誰かに案内してもらいますか?

また、この投稿にはいくつかの重複の可能性があります-Javaでのバイナリ検索、Javaでのバイナリ検索など。プログラムの実装ではなく、コードのレビューに助けが必要です:)

4

3 に答える 3

0

二分木とは何かを明確にしてみましょう。うまくいけば、コードを書くのが少し楽になるでしょう。

二分探索は、ツリーに散在する変数の集まりと考えることができます。たとえば、ツリーのルートまたはトップの数字が 8 の場合、左側にあるものはすべて 8 以下であり、そのノードの右側に分岐するものはすべて 8 より大きくなります。

于 2013-05-07T23:34:40.493 に答える
0

正しいアルゴリズムを使用しているかどうかに関係なく、コードが ArrayOutOfBoundsException をスローしている理由は、i をインクリメントまたはデクリメントするとフラグが false に設定される場合に、i をインクリメントまたはデクリメントし続けるためです。ループ反復に入って一致が見つかった場合は、ループから抜け出します。他の 2 つのケースでは、ループをインクリメント/デクリメントしてから再度チェックしますが、フラグが変更されても中断しません。これは、while または do/while ループを使用した方がよい場合です。インクリメントまたはデクリメントの後の 2 番目のチェックを削除すると、目的が達成されます。

アルゴリズムに関する限り、配列インデックスをインクリメントするのではなく、配列を通過するたびに検索範囲を半分に削減しています。

これを取り除くと便利なことは、例外とスタック トレースが、何が問題なのか (配列インデックスは -1)、どこで発生したか、メソッドと行 (ArraysPract.BinarySearch.findElement(BinarySearch.java:82) で) を教えてくれることです。

于 2013-05-07T23:48:40.647 に答える