Flink.Thomas - 1 year ago 66

Java Question

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 Source

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:

- The array was not sorted. Binary search only works on sorted arrays, therefore the
`Arrays.sort(a)`

command. - The
`binarySearch`

returned a`boolean`

and not a`Result`

object, which is what you wanted to print out.