Searching for elements in large datasets is a common task in computer programming, and doing it efficiently can greatly improve performance. One such efficient method is binary search—an algorithm designed specifically for sorted data. In this blog post, we’ll walk through how binary search works conceptually and then explore a working Java program that performs binary search on a user-provided set of numbers.

What is Binary Search?

Binary search is a divide-and-conquer algorithm used to find the position of a target value within a sorted array. Rather than checking each element one by one like a linear search, binary search repeatedly divides the array into two halves and compares the target with the middle element.

How Binary Search Works:

1. Start with the middle element of the array.
2. If the middle element is the target, return its index.
3. If the target is smaller, repeat the search on the left half.
4. If the target is greater, repeat the search on the right half.
5. Continue this process until the element is found or the sub-array size becomes zero.

Because it halves the number of elements to be checked each time, binary search has a time complexity of O(log n), making it much faster than linear search for large datasets.

Java Code

import java.util.Scanner;

public class BinarySearchDemo {
    public static void main(String[] args) {
        Scanner inputScanner = new Scanner(System.in);
        int[] numberArray;
        int arraySize, searchKey, searchResult;
        String continueSearch;

        // Ask the user for number of elements
        System.out.print("Enter how many numbers to be stored: ");
        arraySize = inputScanner.nextInt();

        numberArray = new int[arraySize];
        System.out.println("Enter " + arraySize + " numbers in INCREASING ORDER:");

        // Read the sorted elements into the array
        for (int index = 0; index < arraySize; index++) {
            System.out.print("Element [" + (index + 1) + "]: ");
            numberArray[index] = inputScanner.nextInt();
        }

        // Repeat search until user decides to stop
        do {
            // Read the number to be searched
            System.out.print("Enter the number to search: ");
            searchKey = inputScanner.nextInt();

            // Call binary search method
            searchResult = performBinarySearch(numberArray, searchKey);

            // Print result based on search outcome
            if (searchResult == -1) {
                System.out.println("Number NOT found in the array.");
            } else {
                System.out.println("Number " + searchKey + " found at position " + (searchResult + 1));
            }

            // Ask if user wants to continue
            System.out.print("Want to search another number? (y/n): ");
            continueSearch = inputScanner.next();

        } while (continueSearch.equalsIgnoreCase("y"));

        inputScanner.close(); // Close the scanner
    }

    /**
     * Method that performs binary search on a sorted array.
     *
     * @param arr the sorted array of integers
     * @param key the integer to search for
     * @return the index of key if found; -1 otherwise
     */
    public static int performBinarySearch(int[] arr, int key) {
        int low = 0, high = arr.length - 1;

        // Continue searching while range is valid
        while (low <= high) {
            int mid = (low + high) / 2; // Calculate midpoint

            // If the middle element is the key, return index
            if (arr[mid] == key)
                return mid;
            // If key is greater, ignore left half
            else if (key > arr[mid])
                low = mid + 1;
            // If key is smaller, ignore right half
            else
                high = mid - 1;
        }
        return -1; // Return -1 if not found
    }
}

How the Code Works

1. The program first takes the size of the array and the elements in increasing order.
2. It then asks the user to enter a number to search.
3. The performBinarySearch function is called to locate the number:
   • It calculates the mid index and compares the key.
   • If the key is found, it returns the index.
   • If not, it adjusts low and high to narrow the search space.
4. The user can repeat this process until they choose not to.

Sample Input/Output

Enter how many numbers to be stored: 5
Enter 5 numbers in INCREASING ORDER:
Element [1]: 10
Element [2]: 20
Element [3]: 30
Element [4]: 40
Element [5]: 45
Enter the number to search: 40
Number 40 found at position 4
Want to search another number? (y/n): y
Enter the number to search: 10
Number 10 found at position 1
Want to search another number? (y/n): y
Enter the number to search: 25
Number NOT found in the array.
Want to search another number? (y/n): n

Output Explanation

Let’s break down each interaction in the sample run:

1. Searching for 40:

• The list is: [10, 20, 30, 40, 45]
• low = 0, high = 4 → mid = 2 → element at index 2 is 30
• Since 40 > 30, set low = 3
• New mid = (3 + 4) / 2 = 3 → element at index 3 is 40, which matches the search key
• Output: Number 40 found at position 4 (1-based index)

2. Searching for 10:

• low = 0, high = 4 → mid = 2 → element at index 2 is 30
• Since 10 < 30, set high = 1
• New mid = (0 + 1) / 2 = 0 → element at index 0 is 10, which matches the key
• Output: Number 10 found at position 1

3. Searching for 25:

• low = 0, high = 4 → mid = 2 → element at index 2 is 30
• Since 25 < 30, set high = 1
• New mid = 0 → element at index 0 is 10
• Since 25 > 10, set low = 1, mid = 1 → element at index 1 is 20
• Since 25 > 20, set low = 2
• Now low > high → search stops
• Output: Number NOT found in the array.

Each of these cases shows how binary search quickly narrows down the range of possible positions, offering fast search times compared to linear scanning.