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 回答