java - 二分搜索递归猜测数字

Question

我正在编写一个二进制搜索算法，我想知道搜索我提供的数字所需的最小猜测数。假设我提供的数字是 33，那么它应该计算 7 个步骤。

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

所以这是我的代码

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;
    }

}

我创建了一个单独的方法。这是我的主课..

package binarySearch;

public class MainClass {
    public static void main (String[] args){

        Binary search= new Binary();

        search.search(1, 100,33 );

    }
}

在这里，我将下限设为 1，将上限设为 100，而我要计算的猜测数是 33。但是当我执行代码时，我得到的计数是 68..但是根据二进制搜索它应该是 7

Answer 1

看一下您创建下一个猜测的行:

gussedNo=upperBound+lowerBound/2;

由于 Java 中的数学运算符优先级，这一行等同于:

gussedNo=upperBound+(lowerBound/2);

这显然没有执行二进制搜索，因此不是您想要的。您可以通过显式添加括号来解决此问题:

gussedNo = (upperBound + lowerBound) / 2;