问题描述:

I'm working on a program that will ask the user to input a value between 3000-3100 and do a binary search and show how many comparisons it made. Overall the search part of the program is working fine; however, my professor wants me to print the program doing the math. For example, I need the program to show the computer doing the binary search math, and show the comparisons it takes for the program to find the inputted number.

I have a comparisonCount that I'm incrementing it when I do a comparison, but the results aren't what I think they should be. For example, my professor said if you input 3067 there should be 7 comparisons, but currently the program is saying 4, and the counter is saying 3.

Can you help me find the reason for the discrepancy?

Here's the code:

package binary.search;

import java.util.Scanner;

public class BinarySearch

{

public static void binarySearch(int[] array, int lowerbound, int upperbound, int key)

{

int position;

int comparisonCount = 1; // counting the number of comparisons

// To start, find the subscript of the middle position.

position = (lowerbound + upperbound) / 2;

//System.out.println();

while ((array[position] != key) && (lowerbound <= upperbound))

{

comparisonCount++;

if (array[position] > key) // If the number is > key, ..

{

upperbound = position - 1; // decrease position by one.

}

else

{

lowerbound = position + 1; // Else, increase position by one.

}

position = (lowerbound + upperbound) / 2;

}

if (lowerbound <= upperbound)

{

System.out.println("The number " + key + " was found in array.");

System.out.println("The binary search found the number after " + comparisonCount + " comparisons.");

}

else

System.out.println("That number is not in this array. The binary search completed "

+ comparisonCount + " comparisons.");

}

public static void main(String[] args)

{

// Set up variables

int arrLength = 100;

Scanner inp = new Scanner(System.in);

int[] num = new int[arrLength]; //Create array

int repeat = 1; //Boolean for repeat loop

char yesNo;

int upperLim = 3100;

int lowerLim = 3000;

//Populate array

while (repeat == 1)

{

int value = 0;

int valid = 0;

for (int i = 0; i < num.length; i++)

{

num[i] = i + lowerLim;

}

//Get integer from user

do

{

System.out.print("Please enter a number between " + lowerLim + " and " + upperLim + ": ");

value = inp.nextInt();

if (value < lowerLim || value > upperLim)

{

System.out.print("That wasn't a valid number. Please try again. \n");

}

}

while (value < lowerLim || value > upperLim);

//Run binary search

binarySearch(num, 0, arrLength - 1, value);

do

{

valid = 0;

System.out.print("Would you like to rerun the program? Y for yes, N for no.\n");

yesNo = (inp.next()).charAt(0);

if (yesNo == 'Y')

{

repeat = 1;

valid = 1;

}

else if (yesNo == 'N')

{

repeat = 0;

valid = 1;

}

else

System.out.print("Not a valid response. \n");

}

while (valid != 1);

}

}

}

网友答案:

Seven iterations is the maximum that it would take to find a number in a set of one hundred. That's because log2100 is somewhere between six and seven and you need to use the higher of those two values to be certain of finding it.

However, it may be less for certain specific values because of the way it works. Let's change your code so that it outputs what it's doing at each stage (just a few added outputs, sections marked with //<<here to //<<):

while ((array[position] != key) && (lowerbound <= upperbound)) {
    System.out.print(String.format(                        //<<here
        "Step %d, lo=%2d, hi=%2d, mid=%2d, [mid]=%4d, ", 
        comparisonCount, lowerbound, upperbound,
        position, array[position]));                       //<<
    comparisonCount++;
    if (array[position] > key) {
        upperbound = position - 1;
        System.out.println(String.format(                  //<<here
            "too high, hi:=%2d", upperbound));             //<<
    } else {
        lowerbound = position + 1;
        System.out.println(String.format(                  //<<here
            "too low,  lo:=%2d", lowerbound));             //<<
    }
    position = (lowerbound + upperbound) / 2;
}
if (lowerbound <= upperbound) {
    System.out.println(String.format(                      //<<here
        "Step %d, lo=%2d, hi=%2d, mid=%2d, [mid]=%4d, found!", 
        comparisonCount, lowerbound, upperbound,
        position, array[position]));                       //<<
    System.out.println("The number " + key +
        " was found in array.");
    System.out.println("The binary search found the number after "
        + comparisonCount + " comparisons.");
}

For example, if you're searching for 3049, you'll basically find that straight away:

Step 1: lo= 0, hi=99, mid=49, [mid]=3049, found!

For your specific value of 3067, it goes like this:

Step 1: lo= 0, hi=99, mid=49, [mid]=3049, too low,  lo:=50
Step 2: lo=50, hi=99, mid=74, [mid]=3074, too high, hi:=73
Step 3: lo=50, hi=73, mid=61, [mid]=3061, too low,  lo:=62
Step 4: lo=62, hi=73, mid=67, [mid]=3067, found!

Hence four iterations, as you're seeing. If you want to see the full seven iterations, you can just search for 3099:

Step 1, lo= 0, hi=99, mid=49, [mid]=3049, too low,  lo:=50
Step 2, lo=50, hi=99, mid=74, [mid]=3074, too low,  lo:=75
Step 3, lo=75, hi=99, mid=87, [mid]=3087, too low,  lo:=88
Step 4, lo=88, hi=99, mid=93, [mid]=3093, too low,  lo:=94
Step 5, lo=94, hi=99, mid=96, [mid]=3096, too low,  lo:=97
Step 6, lo=97, hi=99, mid=98, [mid]=3098, too low,  lo:=99
Step 7, lo=99, hi=99, mid=99, [mid]=3099, found!
相关阅读:
Top