问题描述:

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 `log`

is somewhere between six and seven and you need to use the higher of those two values to be certain of finding it._{2}100

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!
```