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.");}elseSystem.out.println("That number is not in this array. The binary search completed "+ comparisonCount + " comparisons.");}public static void main(String[] args){// Set up variablesint arrLength = 100;Scanner inp = new Scanner(System.in);int[] num = new int[arrLength]; //Create arrayint repeat = 1; //Boolean for repeat loopchar yesNo;int upperLim = 3100;int lowerLim = 3000;//Populate arraywhile (repeat == 1){int value = 0;int valid = 0;for (int i = 0; i < num.length; i++){num[i] = i + lowerLim;}//Get integer from userdo{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 searchbinarySearch(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;}elseSystem.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