0


私は二分探索の概念にかなり慣れていないので、個人的な練習のために Java でこれを行うプログラムを作成しようとしています。この概念はよく理解していますが、コードが機能していません。

私のコードで実行時例外が発生し、それが原因で Eclipse がクラッシュし、その後、コンピューターがクラッシュしました... ただし、ここにはコンパイル時エラーはありません。

これが私がこれまでに持っているものです：

public class BinarySearch
{
    // instance variables
    int[] arr;
    int iterations;

    // constructor
    public BinarySearch(int[] arr)
    {
        this.arr = arr;
        iterations = 0;
    }

    // instance method
    public int findTarget(int targ, int[] sorted)
    {
        int firstIndex = 1;
        int lastIndex = sorted.length;
        int middleIndex = (firstIndex + lastIndex) / 2;
        int result = sorted[middleIndex - 1];

        while(result != targ)
        {
            if(result > targ)
            {
                firstIndex = middleIndex + 1;
                middleIndex = (firstIndex + lastIndex) / 2;
                result = sorted[middleIndex - 1];

                iterations++;
            }
            else
            {
                lastIndex = middleIndex + 1;
                middleIndex = (firstIndex + lastIndex) / 2;
                result = sorted[middleIndex - 1];

                iterations++;
            }
        }
        return result;
    }


    // main method
    public static void main(String[] args)
    {
        int[] sortedArr = new int[]
        {
            1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29
        };
        BinarySearch obj = new BinarySearch(sortedArr);

        int target = sortedArr[8];
        int result = obj.findTarget(target, sortedArr);

        System.out.println("The original target was -- " + target + ".\n" +
                            "The result found was -- " + result + ".\n" +
                            "This took " + obj.iterations + " iterations to find.");        
    } // end of main method
} // end of class BinarySearch
4

4 に答える 4

3 
int result = sorted[middleIndex - 1];

する必要があります

int result = sorted[middleIndex];

の場合lastIndex = 1、にアクセスしようとしますsorted[-1]。

と

lastIndex = middleIndex + 1;

する必要があります

lastIndex = middleIndex - 1;

または、の終わりを超えてアクセスしようとする場合がありますsorted。

そして、完全を期すために含まれている、Ted Hoppが発見したように、あなたは

firstIndex = 0;
lastIndex = sorted.length-1;

配列インデックスは0ベースであるため。

于 2012-10-14T21:29:19.490 に答える
3

Javaでは、配列のインデックス付けはゼロベースです。つまり、インデックスの有効な範囲は0から配列の長さまでですが、配列の長さは含まれません。1から配列の長さまでインデックスを作成しています。これを置き換えてみてください：

int firstIndex = 1;
int lastIndex = sorted.length;

と：

int firstIndex = 0;
int lastIndex = sorted.length - 1;

また、@ Danielが彼の回答で指摘しているように、更新する場合lastIndexは、更新する必要がありますmiddleIndex - 1（middleIndex + 1現在のようにではなく）。

于 2012-10-14T21:29:32.860 に答える
1

メソッドfindTarget（）のwhileループは、無限に実行されています。したがって、実行時に発生するエラーは、メモリが永遠に実行され続けるため、メモリに関連するものであると推測しています。findTarget（）メソッドの変更を検討しますか？はいの場合は、以下のサンプルを試してください。

                 int firstIndex = 0;
                 int lastIndex = sorted.length-1;
                while (firstIndex <= lastIndex) {
                    middleIndex = (firstIndex + lastIndex) / 2;
                    if (sorted[middleIndex] == targ) {

                            return middleIndex;
                    } else if (sorted[middleIndex] < targ) {
                         iterations++;
                        firstIndex = middleIndex + 1;
                    } else {
                         iterations++;
                           lastIndex = middleIndex - 1;
                    }
            }
            return -1;
于 2012-10-14T21:48:08.840 に答える
0


インデックス ロジックがオフになっただけでなく (Ted と Daniel が上記で指摘したように)、if ステートメント内のコード ブロックを else のコード ブロックと切り替える必要があります。

修正されたコードは次のとおりです。

public class BinarySearch
{
    // instance variables
    int[] arr;
    int iterations;

    // constructor
    public BinarySearch(int[] arr)
    {
        this.arr = arr;
        iterations = 0;
    }

    // instance method
    public int findTarget(int targ, int[] sorted)
    {
        int firstIndex = 0;
        int lastIndex = sorted.length - 1;
        int middleIndex = (firstIndex + lastIndex) / 2;
        int result = sorted[middleIndex];

        iterations++;

        while(result != targ)
        {
            if(result > targ)
            {
                lastIndex = middleIndex - 1;
                middleIndex = (firstIndex + lastIndex) / 2;
                result = sorted[middleIndex];

                iterations++;
            }
            else
            {
                firstIndex = middleIndex + 1;
                middleIndex = (firstIndex + lastIndex) / 2;
                result = sorted[middleIndex];

                iterations++;
            }
        }
        return result;
    }

    // main method
    public static void main(String[] args)
    {
        int[] sortedArr = new int[]
        {
            1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29
        };
        BinarySearch obj = new BinarySearch(sortedArr);

        int target = sortedArr[8];
        int result = obj.findTarget(target, sortedArr);

        System.out.println("The original target was -- " + target + ".\n" +
                "The result found was -- " + result + ".\n" +
                "This took " + obj.iterations + " iterations to find.");        
    } // end of main method
} // end of class BinarySearch
于 2012-10-18T02:50:00.013 に答える