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


here is your problem gussedNo=upperBound+lowerBound/2;



you forgot to complete the order of trims abour must be gussedNo=(upperBound+lowerBound)/2;

+1


source







All Articles