Binary search guessing a number recursively
I am coding for a binary search algorithm and I want to have minimal counting guesses to find the number I provide. Suppose the number I provide is 33, then it should count 7 steps.
Step no number guessed result range of possible values
0 1-100
1 50 too high 1-49
2 25 too low 26-49
3 37 too high 26-36
4 31 too low 32-36
5 34 too high 32-33
6 32 too low 33-33
7 33 correct
so this is my code for this
package binarySearch;
public class Binary {
int gussedNo;
public static int count =0;
void search(int lowerBound,int upperBound,int num){
gussedNo=upperBound+lowerBound/2;
count();
if(gussedNo==num){
System.out.println(count);}
else if(gussedNo>num){
upperBound=gussedNo-1;
search(lowerBound,upperBound,num);
}
if(gussedNo<num){
lowerBound=gussedNo+1;
search(lowerBound,upperBound,num);
}
}
int count(){
count=count+1;
return count;
}
}
I created a separate method. here is my my main class ..
package binarySearch;
public class MainClass {
public static void main (String[] args){
Binary search= new Binary();
search.search(1, 100,33 );
}
}
Here I gave lowerbound as 1 and uperbound as 100 and the number I want to count the guesses for it is 33. But when I execute the code I get a score of 68. but it should be 7 according to binary search
+3
source to share
2 answers
Look at the line where you make the following guess:
gussedNo=upperBound+lowerBound/2;
Due to the precedence of the mathematical operators in Java, this line is the same as:
gussedNo=upperBound+(lowerBound/2);
Which obviously does not do a binary search, and therefore not what you wanted. You can fix this problem by explicitly adding parentheses:
gussedNo = (upperBound + lowerBound) / 2;
+3
source to share