Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.


public class BinarySearch {
    public int binarySearch(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] < x)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int[] arr = {2, 3, 4, 10, 40};
        int result = bs.binarySearch(arr, 10);
        System.out.println(result != -1 ? "Element found at index " + result : "Element not found");
    }
}

Key Points

Binary search works best on sorted arrays. The time complexity is O(log n), making it much faster than linear search for large datasets.

Console Output:

Element found at index 3

Binary Search: Recursive Approach

Recursive Binary Search

In the recursive approach, binary search is implemented using recursion. This method divides the array into subarrays and applies the binary search logic recursively.


public class RecursiveBinarySearch {
    public int binarySearch(int[] arr, int left, int right, int x) {
        if (right >= left) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, left, mid - 1, x);
            return binarySearch(arr, mid + 1, right, x);
        }
        return -1;
    }
    public static void main(String[] args) {
        RecursiveBinarySearch rbs = new RecursiveBinarySearch();
        int[] arr = {1, 2, 3, 4, 5};
        int result = rbs.binarySearch(arr, 0, arr.length - 1, 4);
        System.out.println(result != -1 ? "Element found at index " + result : "Element not found");
    }
}

Considerations

The recursive approach is elegant but involves additional overhead due to recursive function calls. It may lead to stack overflow for large arrays.

Console Output:

Element found at index 3

Binary Search: Applications

Applications of Binary Search

Binary search is widely used in real-world applications such as searching in databases, implementing dictionaries, and solving algorithmic problems that require efficient search operations.


// Example: Finding the square root using binary search
public class SquareRootBinarySearch {
    public double squareRoot(double number) {
        double precision = 0.00001;
        double start = 0, end = number;
        double mid = 0;
        while ((end - start) > precision) {
            mid = (start + end) / 2;
            if (mid * mid == number)
                return mid;
            else if (mid * mid < number)
                start = mid;
            else
                end = mid;
        }
        return mid;
    }
    public static void main(String[] args) {
        SquareRootBinarySearch sqrtBS = new SquareRootBinarySearch();
        double result = sqrtBS.squareRoot(50);
        System.out.println("Square root of 50 is approximately " + result);
    }
}

Real-World Use

Binary search can be adapted for various applications beyond simple number searches, such as finding the square root, as demonstrated above.

Console Output:

Square root of 50 is approximately 7.07106

Binary Search: Variations

Finding First or Last Occurrence

Binary search can be modified to find the first or last occurrence of a target element in a sorted array. This is useful in scenarios where duplicates exist, and specific occurrences are needed.


public class FirstLastOccurrence {
    public int findFirstOccurrence(int[] arr, int x) {
        int left = 0, right = arr.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) {
                result = mid;
                right = mid - 1;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        FirstLastOccurrence flo = new FirstLastOccurrence();
        int[] arr = {1, 2, 2, 2, 3, 4, 5};
        int firstOccurrence = flo.findFirstOccurrence(arr, 2);
        System.out.println("First occurrence of 2 is at index " + firstOccurrence);
    }
}

Advanced Usage

Modifying binary search to find specific occurrences enhances its utility, especially in data analysis and processing tasks where precise element positions are crucial.

Console Output:

First occurrence of 2 is at index 1

Binary Search: Real-World Example

Implementing Binary Search in a Library System

Consider a library system where books are sorted by ISBN numbers. Binary search can be used to quickly locate a book using its ISBN.


public class LibrarySystem {
    public int findBookByISBN(int[] isbns, int isbn) {
        int left = 0, right = isbns.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isbns[mid] == isbn)
                return mid;
            if (isbns[mid] < isbn)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        LibrarySystem ls = new LibrarySystem();
        int[] isbns = {1001, 1002, 1003, 1004, 1005};
        int result = ls.findBookByISBN(isbns, 1003);
        System.out.println(result != -1 ? "Book found at index " + result : "Book not found");
    }
}

Practical Implementation

Using binary search in systems like libraries ensures rapid retrieval of information, enhancing user experience and operational efficiency.

Console Output:

Book found at index 2