二分查找不停？

Question

我有下面的二分查找法和下面的驱动代码。我在输出中搜索的两个值都存在于数组中。

搜索方法

    //Method for binary search. This method will also cut our array
    public static int binarySearch(int[] nums, int x) {
        //Bounds
        int l = 0, r = nums.length - 1;
        //While the size of the array is not 1
        while (l <= r) {
            //Middle element
            int m = l + (r - 1) / 2;
            //If our element is the middle
            if (nums[m] == x) return m;
            //If x is greater, cut to right half
            else if (x > nums[m]) l = m + 1;
            //Else, ignore right half
            else r = m - 1;
        }
        //If we didn't find the element
        return -1;
    }

驱动程序代码和输出

public class searcher {
    public static void main(String[] args) {
         /* Initialize a new scanner for user input, initialize random for the
        computer to pick a number */
        Scanner s = new Scanner(System.in);
        //Variable for user input
        int guess;
        //Do-while loop
        do {
            System.out.println("Enter a number to search for (0 to quit): ");
            //Get the user's guess
            guess = s.nextInt();
            //Search for the guess in the array of numbers
            int i = binarySearch(nums, guess);
            System.out.println(i);
            //If the number is not found
            if (i == -1) {
                System.out.println("Your number does not occur in this list.");
            }
            //If it is
            else {
                System.out.println("Your number occurs at position " + i);
            }
        } while (guess != 0);
    }
}
/*
Output
Enter a number to search for (0 to quit): 
1
1
Your number occurs at position 1
Enter a number to search for (0 to quit): 
90 
            <------- Program doesn't stop running from here...? */

如果找到，我希望得到输入数字索引的输出，如果没有，该方法应该 return -1 以便我可以打印未找到

Answer 1

int m = l + (r - 1) / 2; // this is not correct, you are subtracting "1"

您需要减去 "left"（为清楚起见编辑了变量名称）：

int mid = left + (right - left) / 2;

或者，更好一点：

int mid = (left+ right) >>> 1;

Answer 2

你减去 1 两次。

r = nums.length - 1;

然后

int m = l + (r - 1) / 2;

应该是

int m = l + (r - l) / 2;

二分查找不停？

Binary search doesn't stop?

java

arrays

algorithm

binary-search