java - 二进制搜索程序打印错误

Question

大家好，我正在研究二分查找程序。我的算法是正确的，但是当我用驱动程序运行程序时，我得到了重复的值“false”，而不是看起来像这样的表。 Table output(LINK)

这是我的驱动程序和主程序。

public class TestResulter {

public static void main(String[] args) {
    //Resulter resulter = new Resulter();
    int numberOfItems = 10000;
    int item;
    int a[ ] = new int[ numberOfItems ];


    for( int i = 0; i < 20; i++ )
    {
        item = Resulter.randomitem( a );
        System.out.println( Resulter.binarySearch( a , item ) );
    }


}

}

我的 binarySearch 算法的主程序。

import java.util.Random;

public class Resulter extends TestResulter {
private static class Result {
    public Boolean found; // true if found, false if not found
    public int index; // index where item was found, -1 if not found
    public int steps; // number of comparisons performed

    public Result(boolean f, int ind, int st) {
        found = f;
        index = ind;
        steps = st;
    }

    @Override
    public String toString() {
        return "Result [found=" + found + ", index=" + index + ", steps=" + steps + "]";
    }
}

public static boolean binarySearch(int[] a, int item) { 
    int start=0, end=a.length-1;
    while(end>=start) { 
        int mid = start + ((end - start) / 2);
        if (a[mid] == item) 
            return true; 
        if (a[mid] > item) 
            end = mid-1; 
        else start = mid+1;
    } 
    return false;
}


public static  int  randomitem ( int[] a ) {
    int i;
    Random random = new Random();
    int item = random.nextInt( 10999 );
    for( i = 0; i < 10000; i++ )
    {
        a[ i ] = random.nextInt( 10000 );
    }
    return item;
}
}

我希望我的程序具有与我的线性搜索程序的图像相似的输出。

Answer 1

这是您的代码，其中包含一些更改和重构:

public class TestResulter
{
    public static void main(String[] args)
    {
        int numberOfItems = 10000;
        int item;
        int[] a = new int[numberOfItems];
        fillArray(a);

        for( int i = 0; i < 20; i++ )
        {
            item = Resulter.randomitem(a);
            System.out.println(Resulter.binarySearch(a, item));
        }
    }

    private static void fillArray(int[] a)
    {
        Random random = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = random.nextInt(10000);
        Arrays.sort(a);
    }
} 

public class Resulter
{
    private static class Result
    {
        public boolean found; // true if found, false if not found
        public int index; // index where item was found, -1 if not found
        public int steps; // number of comparisons performed

        public Result(boolean f, int ind, int st)
        {
            found = f;
            index = ind;
            steps = st;
        }

        @Override
        public String toString()
        {
            return "Result [found=" + found + ", index=" + index + ", steps=" + steps + "]";
        }
    }

    public static Result binarySearch(int[] a, int item)
    {
        int start=0, end=a.length-1;
        int stepCount = 0;
        while(end>=start)
        {
            stepCount++;
            int mid = start + ((end - start) / 2);
            if(a[mid] == item)
                return new Result(true, mid, stepCount);
            else if(a[mid] > item)
                end = mid-1;
            else
                start = mid+1;
        }
        return new Result(false, -1, stepCount);
    }


    public static int randomitem(int[] a)
    {
        return new Random().nextInt(10000);
    }
}

在我看来，您的解决方案中的主要问题是:

1. 数组未排序。二分查找仅适用于排序数组，因此 Arrays.sort(a) 命令。
2. binarySearch 返回了一个 boolean 而不是 Result 对象，后者正是您要打印的内容。