Time and Space Complexity of Binary Search

Time Complexity — O(log N)

Binary search operates by repeatedly dividing the array in half. Each iteration reduces the search space to half of its previous size. Starting with N elements, the size becomes N/2, then N/4, and so forth untill the element is found or the size reaches one. The maximum number of iterations required is log N, where N represents the total number of elements in the array.

Space Complexity — O(1)

The algorithm uses constant extra space since it operates directly on the input data without requiring additional memory allocation.

Template I

int search(int[] arr, int key) {
    if (arr == null || arr.length == 0) return -1;

    int start = 0, end = arr.length - 1;
    while (start <= end) {
        int middle = start + ((end - start) >> 1);
        if (arr[middle] == key) {
            return middle;
        } else if (arr[middle] < key) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }
    return -1;
}

Analysis

• Standard binary search implementation.
• Initial state: start = 0, end = length - 1.
• Loop terminates when start > end.
• Left move: end = middle - 1.
• Right move: start = middle + 1.

Aplication Scenarios

• Suitable for searching values accessible via single index access.
• Conditions can be evaluated independently of adjacent elements.
• No post-processing needed as the loop checks for match at every step.

Template II

int search(int[] arr, int key) {
    if (arr == null || arr.length == 0) return -1;

    int start = 0, end = arr.length;
    while (start < end) {
        int middle = start + ((end - start) >> 1);
        if (arr[middle] == key) {
            return middle;
        } else if (arr[middle] < key) {
            start = middle + 1;
        } else {
            end = middle;
        }
    }

    if (start != arr.length && arr[start] == key) return start;
    return -1;
}

Analysis

• Advanced version of binary search.
• Initial state: start = 0, end = length.
• Loop ends when start == end.
• Left move: end = middle.
• Right move: start = middle + 1.

Application Scenarios

• Requires checking the immediate right neighbor of an element.
• Decision-making based on right neighbor value.
• Ensures at least two elements remain in the search space during each step.
• Post-processing required upon termination to validate the final element.

Template III

int search(int[] arr, int key) {
    if (arr == null || arr.length == 0) return -1;

    int left = 0, right = arr.length - 1;
    while (left + 1 < right) {
        int middle = left + ((right - left) >> 1);
        if (arr[middle] == key) {
            return middle;
        } else if (arr[middle] < key) {
            left = middle;
        } else {
            right = middle;
        }
    }

    if (arr[left] == key) return left;
    if (arr[right] == key) return right;
    return -1;
}

Analysis

• Another advanced variant of binary search.
• Initial setup: left = 0, right = length - 1.
• Termination condition: left + 1 == right.
• Left adjustment: right = middle.
• Right adjustment: left = middle.

Application Scenarios

• When conditions depend on both immediate neighbors of an element.
• Decisions are made based on comparisons with left and right neighbors.
• Maintains a minimum of three elements in the search range at all time.
• Post-processing is necessary after loop completion to verify remaining elements.