prognatis prognatis - 23 days ago 6
Java Question

Beginning Java - Creating a successful binary search algorithm

Design an application that has an array of at least 20 integers. It should call a module that uses the sequential search algorithm to locate one of the values. The module should keep a count of the number of comparisons it makes until it finds the value. Then the program should call another module that uses the binary search algorithm to locate the same value. It should also keep a count of the number of comparisons it makes. Display these values on the screen.

I already have the sequential search working properly, and it displays the number of iterations it took to find the desired value. However, I am having trouble with my binary search module. Every time it searches for a value, it always returns the value 1. Here is the code I have excluding the sequential search module.

Appreciate any help.

//Scanner class
import java.util.Scanner;
public class JavaProgramCh9Ex7_test {

//global scanner to read input
static Scanner keyboard = new Scanner(System.in);

//size of array
final static int SIZE = 20;

//main
public static void main(String[] args) {

//populate the array
int [] twentyNumbers = new int [SIZE];
populateTwentyNumbersArray(twentyNumbers);

//sort the numbers using bubble sorting:
bubbleSort(twentyNumbers);
displayTwentyNumbersSorted(twentyNumbers);

//ask the user for a value to search for:
int desiredValue = getValidInteger("Search for a number", 1, 20);

//start the binary search algorithm:
int binSearchComparison = performBinarySearch (twentyNumbers, desiredValue);
System.out.println(binSearchComparison);

}

//Display the 20 integers in the array in ascending-order:
public static void displayTwentyNumbersSorted (int [] numArray){
System.out.println("");
System.out.println("Here are the 20 numbers sorted in ascending-order");
for (int i = 0; i < numArray.length; i++) {
if(i < 19){
System.err.print(numArray[i] + ", ");
}
else{
System.err.print(numArray[i]);
}
}
}

//Perform the binary search for the user's desired value:
public static int performBinarySearch (int [] numArray, int userValue){
int first = 0;
int middle;
int last = (numArray.length - 1);
int iteration = -1;
boolean found = false;
for (int i = 0; i < numArray.length; i++) {
while ((!found) && (first <= last)) {
middle = ((first + last) / 2);
if (numArray [middle] == userValue) {
found = true;
iteration = (i + 1);
}
if(numArray [middle] > userValue) {
last = (middle - 1);
}

if(numArray [middle] < userValue) {
first = (middle + 1);
}
}
}
return iteration;
}

//Populate the array with 20 random integers:
public static void populateTwentyNumbersArray (int [] numArray){
int number = 0;
for (int i = 0; i < numArray.length; i++) {
do{
number = getRandomNumber(1, 20);
}while (checkNum(numArray, number));
numArray[i] = number;
}
}

//Check to make sure the number is unique:
public static boolean checkNum (int [] numArray, int num) {
boolean value = false;
for (int i = 0; i < numArray.length; i++) {
if (numArray[i] == num) {
value = true;
}
}
return value;
}

//Sort the array in ascending order
public static void bubbleSort(int [] numArray){
int temp;
int maxElement;
for(maxElement = (SIZE - 1); maxElement > 0; maxElement--){
for(int i = 0; i <= (maxElement - 1); i++){
if(numArray[i] > numArray[i + 1]){
temp = numArray[i];
numArray[i] = numArray[i + 1];
numArray[i + 1] = temp;
}
}
}
}

//Get a valid Integer from the user to determine the number of seats sold per section:
public static int getValidInteger(String msg, int low, int high) {
int newValue = getInteger(msg);

//Check that the user entered a valid number within the range:
while (newValue < low || newValue > high) {
System.err.println("Please enter a number from " + low + " to " + high + ".");
newValue = getInteger(msg);
}
return newValue;
}

//Check for a valid Integer input from the user:
public static int getInteger(String msg) {
System.out.println(msg);
while (!keyboard.hasNextInt()) {
keyboard.nextLine();
System.err.println("Invalid integer. Please try again.");
}
int number = keyboard.nextInt();
keyboard.nextLine(); //flushes the buffer
return number;
}

//Get a random number to represent the computer's choice:
public static int getRandomNumber(int low, int high){
return (int)(Math.random() * ((high + 1) - low)) + low;
}

}

Answer

In your performBinarySearch you check for the all values of array, this maximizes the binary search complexity, though the loop hasn't any effect on searching. If the value present in the array, then the searching function checks whether it is present or not when i=0 and make found=true. After that the inner while loop don't executes as found=true all the times.

For that reason, iterator=(i+1) for i=0 all the times if the value is present in the array, otherwise iterator=-1.

Consider the below performBinarySearch function :

public static int performBinarySearch(int[] numArray, int userValue) {
    int first = 0;
    int middle;
    int last = (numArray.length - 1);
    int iteration = 0;
    boolean found = false;
    while ((!found) && (first <= last)) {
        iteration++;
        middle = ((first + last) / 2);
        if (numArray[middle] == userValue) {
            found = true;
            break;
        }
        if (numArray[middle] > userValue) {
            last = (middle - 1);
        }

        if (numArray[middle] < userValue) {
            first = (middle + 1);
        }
    }
    if (found) return iteration;
    else return -1;
}

Here, I have reused your code with a simple modification. I have deleted your redundant outer loop and calculated the number of iteration each time the while loop executes. If found then make found=true and break the loop(as I have already found the expected value) and return the value.