Back to Basics: Master binary search

Learn how to implement binary search, lower bound, and upper bound algorithms in Java for efficient searching of sorted arrays and lists.

Binary search is a search algorithm used to find a specific element in a sorted list or array. The algorithm works by repeatedly dividing the search interval in half until the target element is found, or until the search interval is empty. Binary search is a very efficient algorithm, with a worst-case time complexity of O(log n).

Lower and upper bounds are variations of binary search that are used to find the first occurrence of a target element in a sorted list or array. Lower bound returns the index of the first element greater than or equal to the target, while the upper bound returns the index of the first element greater than the target.

Binary Search

The binary search algorithm works by dividing the search interval in half and eliminating half of the remaining elements at each step. The algorithm assumes that the list or array is sorted, and compares the target element with the middle element of the search interval.

If the middle element is equal to the target, the algorithm returns the index of the middle element. If the middle element is greater than the target, the search interval is reduced to the lower half of the list or array. If the middle element is less than the target, the search interval is reduced to the upper half of the list or array.

The process is repeated until the target element is found, or until the search interval is empty. Here is an 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) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Lower Bound

The lower bound algorithm is a variation of binary search that is used to find the first occurrence of a target element in a sorted list or array. The algorithm works by dividing the search interval in half and comparing the middle element with the target.

If the middle element is less than the target, the search interval is reduced to the upper half of the list or array. If the middle element is greater than or equal to the target, the search interval is reduced to the lower half of the list or array.

The process is repeated until the search interval is reduced to a single element. The index of this element is the lower bound of the target element. Here is an implementation of the lower bound in Java:

public static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

Upper Bound

The upper bound algorithm is another variation of binary search that is used to find the first occurrence of a target element in a sorted list or array. The algorithm works by dividing the search interval in half and comparing the middle element with the target.

If the middle element is less than or equal to the target, the search interval is reduced to the upper half of the list or array. If the middle element is greater than the target, the search interval is reduced to the lower half of the array.

The process is repeated until the search interval is reduced to a single element. The index of this element is the upper bound of the target element.

Here is an implementation of the upper bound in Java:

public static int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

Examples

Let’s say we have a sorted array of integers:

int[] arr = {1, 2, 3, 3, 3, 4, 4, 5, 6};

To find the index of the first occurrence of the number 3 using binary search, we can call the binarySearch function:

int index = binarySearch(arr, 3);

The result is 2, which is the index of the first occurrence of the number 3 in the array.

To find the lower bound of the number 3 using the lowerBound function, we can call:

int index = lowerBound(arr, 3);

The result is also 2, which is the index of the first occurrence of the number 3 in the array.

To find the upper bound of the number 3 using the upperBound function, we can call:

int index = upperBound(arr, 3);

The result is 5, which is the index of the first element that is greater than the number 3 in the array.

Conclusion

Binary search, lower bound, and upper bound are powerful algorithms that are used to efficiently search sorted lists and arrays. By understanding how these algorithms work and how to implement them in code, you can improve the efficiency of your programs and write more effective algorithms.