ISC Practicals and Theory - Binary Search

Binary search is a method of finding a number in an array by repeatedly halving the part of the array that is still being searched. It is much faster than checking every element one by one, but it works only when the array is already sorted.

Definition

Binary search compares the number to be found (the *key*) with the middle element of the array. If they are equal, the search ends. If the key is larger, it can only be in the right half; if it is smaller, only in the left half. The same step is repeated on that half until the key is found or no elements are left.

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

For the array $5, 12, 19, 27, 34, 41$ and the key $27$:

• Middle element is $19$. $27 > 19$, so search the right half.
• Middle element of $27, 34, 41$ is $34$. $27 < 34$, so search the left part.
• Only $27$ is left and it matches: 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, then compares each element with the next one. If any element is greater than the next, it prints a message and returns false. If not, it returns true.
4. If accept() returned true, main calls display(), which reads the number key to be searched and calls search(key).
5. In search(int key):
   • Set low = 0 and high = n - 1.
   • While low <= high:
     • Find mid = (low + high) / 2.
     • If arr[mid] == key, return mid.
     • If arr[mid] < key, the key lies on the right, so set low = mid + 1.
     • Otherwise the key lies on the left, so set high = mid - 1.
   • If the loop ends without a match, return -1.
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() performs the binary search using a loop, 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 key)
    {
        int low = 0, high = n - 1, mid;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (arr[mid] == key)
                return mid;
            else if (arr[mid] < key)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return -1;
    }

    void display()
    {
        System.out.print("Enter the number to search: ");
        int key = sc.nextInt();
        int pos = search(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): 6
Enter 6 elements in ascending order:
5 12 19 27 34 41
Enter the number to search: 27
27 is present at index 3 (position 4)

Enter the size of the array (2 to 20): 6
Enter 6 elements in ascending order:
5 12 19 27 34 41
Enter the number to search: 30
30 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): 1
Invalid size

Dry run

Input: size 6, array $5, 12, 19, 27, 34, 41$, key $27$. Here n = 6, so low = 0 and high = 5 at the start.

search() returns 3, so the program prints that 27 is present at index 3 (position 4), the same as the first sample run.

Variations

1. Descending order "Write a program to search a number in an array sorted in descending order using binary search."
2. Strings "Search a name in an array of Strings sorted alphabetically using binary search."
3. Sort first "Accept the array in any order, sort it using Bubble Sort and then search a number using binary search."
4. Comparisons "Modify the binary search to count and display the number of comparisons made."