ISC Practicals and Theory - Binary Search (Recursive Technique)

Binary search using the recursive technique finds a number in a sorted array by making the method search() call itself on a smaller part of the array each time, until the number is found or no elements are left.

Definition

In binary search, the number to be found (the *key*) is compared with the middle element of the array. If it matches, the search is over. Otherwise the search continues in the left half (if the key is smaller) or the right half (if the key is larger). A method is recursive when it calls itself; here each call handles a smaller part of the array, and the call that finds the key, or finds nothing left to search, stops the calls.

This program assumes the array is sorted in ascending order. It checks this while taking input and stops with a message if the order is wrong, since binary search gives wrong answers on unsorted data. It also assumes the size is between 2 and 20.

For the array $3, 8, 15, 22, 31, 47, 60$ and the key $47$:

• The middle element is $22$. $47 > 22$, so search the right part $31, 47, 60$.
• Its middle element is $47$: found.

Algorithm

1. In main, create an object ob of the class BinarySearch and call accept().
2. accept() reads the size n. If n is less than 2 or more than 20, it prints Invalid size and returns false.
3. Otherwise it reads n elements into arr and checks that no element is greater than the one after it. If one is, it prints a message and returns false; if not, it returns true.
4. If accept() returned true, main calls display(), which reads key and calls search(0, n - 1, key).
5. The recursive method search(int low, int high, int key):
   • If low > high, no elements are left, so return -1.
   • Find mid = (low + high) / 2.
   • If arr[mid] == key, return mid.
   • If arr[mid] < key, return search(mid + 1, high, key), which searches the right part.
   • Otherwise return search(low, mid - 1, key), which searches the left part.
6. display() prints the index and position if the returned value is not -1, and a "not present" message otherwise.

Program

The method accept() takes and validates the input, search() calls itself to perform the binary search, and display() reads the key and prints the result.

import java.util.Scanner;

public class BinarySearch
{
    Scanner sc = new Scanner(System.in);
    int arr[];
    int n;

    BinarySearch()
    {
        n = 0;
    }

    boolean accept()
    {
        System.out.print("Enter the size of the array (2 to 20): ");
        n = sc.nextInt();
        if (n < 2 || n > 20)
        {
            System.out.println("Invalid size");
            return false;
        }
        arr = new int[n];
        System.out.println("Enter " + n + " elements in ascending order:");
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        for (int i = 0; i < n - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                System.out.println("The array is not in ascending order");
                return false;
            }
        }
        return true;
    }

    int search(int low, int high, int key)
    {
        if (low > high)
            return -1;
        int mid = (low + high) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            return search(mid + 1, high, key);
        else
            return search(low, mid - 1, key);
    }

    void display()
    {
        System.out.print("Enter the number to search: ");
        int key = sc.nextInt();
        int pos = search(0, n - 1, key);
        if (pos == -1)
            System.out.println(key + " is not present in the array");
        else
            System.out.println(key + " is present at index " + pos + " (position " + (pos + 1) + ")");
    }

    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        if (ob.accept())
            ob.display();
    }
}

Variable description table

Sample input and output

Enter the size of the array (2 to 20): 7
Enter 7 elements in ascending order:
3 8 15 22 31 47 60
Enter the number to search: 47
47 is present at index 5 (position 6)

Enter the size of the array (2 to 20): 7
Enter 7 elements in ascending order:
3 8 15 22 31 47 60
Enter the number to search: 10
10 is not present in the array

Enter the size of the array (2 to 20): 5
Enter 5 elements in ascending order:
9 4 20 30 40
The array is not in ascending order

Enter the size of the array (2 to 20): 25
Invalid size

Dry run

Input: size 7, array $3, 8, 15, 22, 31, 47, 60$, key $47$. display() calls search(0, 6, 47).

The value 5 is returned through call 1 to display(), so the program prints that 47 is present at index 5 (position 6), the same as the first sample run.

Variations

1. Count of calls "Modify the recursive binary search to display the number of times the method calls itself."
2. Descending order "Search a number in an array sorted in descending order using the recursive technique."
3. Strings "Search a name in an array of Strings sorted alphabetically using binary search with recursion."