Flink.Thomas Flink.Thomas - 3 months ago 20
Java Question

Binary search program printing false

Hello every one i'm working on a binary search program. My algorithm is correct but when I run the program with the driver program i get back the value "false" repeated instead of a table that looks like this.
Table output(LINK)

here is my driver program and main program.

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 ) );
}


}

}


My main program with binarySearch algorithm.

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;
}
}


I want my program to have a similar output to my image from my linear search program.

Answer

Here is your code with some changes and refactoring:

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);
    }
}

As I see it, the main problems in your solution were:

  1. The array was not sorted. Binary search only works on sorted arrays, therefore the Arrays.sort(a) command.
  2. The binarySearch returned a boolean and not a Result object, which is what you wanted to print out.