Binary Search and its Variations

Binary search is a widely-used technique in computer science and competitive programming. It is an efficient searching algorithm that works on sorted arrays or lists. The binary search algorithm follows a divide-and-conquer strategy to find the desired element efficiently. This article will cover binary search and its popular variations, providing insights into their implementation using Java.

Binary Search

Binary search allows searching for an element in a sorted array by repeatedly dividing the search space in half. It starts by examining the middle element of the array and compares it with the desired value. Based on this comparison, the search space is divided, and the process is repeated on the subarray where the target element might reside. This is why binary search is also called the logarithmic search.

Here is the basic implementation of binary search in Java:

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;

        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1; // Element not found
}

The above implementation returns the index of the target element if found, -1 otherwise.

Variations of Binary Search

Lower Bound

The lower bound binary search variant allows finding the smallest index at which an element can be inserted in a sorted array without violating the sorting. It is also known as the lower bound binary search.

Consider the following implementation of the lower bound binary search:

public static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }

    return left;
}

The lower bound binary search returns the index of the smallest element greater than or equal to the target. If the target is larger than all elements in the array, it returns the array's length.

Upper Bound

The upper bound binary search variant allows finding the smallest index at which an element can be inserted in a sorted array while maintaining the sorting order. It is also known as the upper bound binary search.

Here's an implementation of the upper bound binary search:

public static int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] <= target)
            left = mid + 1;
        else
            right = mid;
    }

    return left;
}

The upper bound binary search returns the index of the smallest element greater than the target. If the target is greater than or equal to all elements in the array, it also returns the array's length.

Conclusion

Binary search is a powerful algorithm for efficient searching in sorted arrays or lists. Its variations, such as the lower bound and upper bound binary searches, provide additional functionalities for finding insertion points in sorted arrays. Understanding and utilizing these variations can significantly improve problem-solving capabilities in competitive programming using Java.