Binary search operates with O(log n) time complexity on a sorted array of n elements. The algorithm repeatedly divides the search interval in half, achieving logarithmic performance.

Algorithm Fundamentals

Binary search, also known as half-interval search, is an efficient algorithm for locating a target value within a sorted sequence. It compares the target to the middle element and eliminates half of the remaining elements from consideration with each step.

Implementation Appproaches

Approach 1: Inclusive Bounds

This method uses a search range where both the left and right boundaries are inclusive. The loop condition is while (left <= right).

Procedure:

1. Set lowerBound = 0 and upperBound = array.length - 1.
2. While lowerBound <= upperBound:
   • Calculate the midpoint: midpoint = (lowerBound + upperBound) >>> 1.
   • If array[midpoint] == target, return midpoint.
   • If target > array[midpoint], set lowerBound = midpoint + 1.
   • If target < array[midpoint], set upperBound = midpoint - 1.
3. Return -1 if the loop exits without finding the target.

Java Code Example:

public class BinarySearchDemo {
    public static int inclusiveBoundsSearch(int[] sortedArray, int key) {
        int low = 0;
        int high = sortedArray.length - 1;
        
        while (low <= high) {
            int center = (low + high) >>> 1;
            if (sortedArray[center] == key) {
                return center;
            } else if (sortedArray[center] < key) {
                low = center + 1;
            } else {
                high = center - 1;
            }
        }
        return -1;
    }
}

Approach 2: Right-Exclusive Bound

This method uses a range where the left bound is inclusive, but the right bound is exclusive. The loop condition is while (left < right). The initial right index is set to array.length.

Procedure Differences:

• Initialize upperBound = array.length.
• Loop condition: while (lowerBound < upperBound).
• When target < array[midpoint], set upperBound = midpoint (since the midpoint is not included in the new exclusive upper bound).

Java Code Example:

public class BinarySearchDemo {
    public static int exclusiveUpperSearch(int[] sortedArray, int key) {
        int low = 0;
        int high = sortedArray.length;
        
        while (low < high) {
            int center = (low + high) >>> 1;
            if (sortedArray[center] == key) {
                return center;
            } else if (sortedArray[center] < key) {
                low = center + 1;
            } else {
                high = center;
            }
        }
        return -1;
    }
}

Critical Implementation Details

Midpoint Calculation: Using (low + high) / 2 risks integer overflow for very large indices. The unsigned right shift >>> 1 is preferred: midpoint = (low + high) >>> 1. This safely performs integer division by two.

Performance Comparison: Linear vs. Binary Search

Linear Search Analysis: For an array of size n, the worst-case number of primitive operations (comparisons and increemnts) is approximately 3n + 3.

Binary Search Analysis: The number of loop iterations in the worst case is floor(log₂(n)) + 1. The total number of primitive operations is approximately 5L + 4, where L is the number of iterations.

Efficiency Comparison:

• For n = 4: Linear ~15 ops, Binary ~19 ops.
• For n = 1024: Linear ~3075 ops, Binary ~59 ops.

As n increases, the number of operations for binary search grows logarithmically (O(log n)), while linear search grows linearly (O(n)). This makes binary search significantly more efficient for large, sorted datasets.

The prerequisite for applying binary search is that the input aray must be sorted. For unsorted data, a linear search or a sort-first approach must be used.