Search code examples
javaarraysalgorithmbinary-search

Binary search doesn't stop?


I have the following binary search method and the following driver code. Both of the values I search for show in the output are present in the array.

Search Method

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

Driver code and output

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...? */

I'm expecting to get an output for the index of the number entered if its found, and if not, the method should return -1 so I can print not found


Solution

  • You are subtracting 1 twice.

    r = nums.length - 1;
    

    and then

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

    should be

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