Binary Search Fundamentals

Problem Statement

Given a sorted array of n integers in ascending order and a target value, implement a function that searches for the target in the array. Return the index if the target exists, otherwise return -1.

Constraints:

• All elements in the array are unique
• n ranges from [1, 10000]
• Each element falls within [-9999, 9999]

Approach

Binary search is commonly applied in three scenarios: finding a specific value, locating the leftmost boundary, and identifying the rightmost boundary.

The problem provides ideal conditions for binary search: an ordered array with no duplicate elements. These characteristics make it suitable for this algorithm.

A crucial aspect of implementing binary search is maintaining interval consistency. The interval definition serves as an invariant that must remain unchanged throughout the search process. Every boundary adjustment within the while loop must adhere to this predefined interval concept, following the principle of loop invraiants.

There are typically two approaches to defining intervals: closed interval [left, right] or half-open interval [left, right).

Implementation Strategies

Closed Interval Approach [left, right]

When using a closed interval [left, right], the while condition employs ≤, meaning left ≤ right. The conditional assignments follow these rules:

• If array[mid] > target, set right = mid - 1
• If array[mid] < target, set left = mid + 1

Code implementation:

public class BinarySearchSolution {
    public int findTarget(int[] data, int targetValue) {
        // Early termination check for out-of-bounds values
        if (targetValue < data[0] || targetValue > data[data.length - 1]) {
            return -1;
        }
        
        int start = 0;
        int end = data.length - 1;
        
        while (start <= end) {
            int midpoint = start + (end - start) / 2;
            
            if (data[midpoint] > targetValue) {
                end = midpoint - 1;
            } else if (data[midpoint] < targetValue) {
                start = midpoint + 1;
            } else {
                return midpoint;
            }
        }
        
        return -1;
    }
}

• Time Complexity: O(log n)
• Space Complexity: O(1)

Half-Open Interval Approach [left, right)

For a half-open interval [left, right), the while condition uses <, meaning left < right. The conditional assignments work as follows:

• If array[mid] > target, set right = mid
• If array[mid] < target, set left = mid + 1

Code implementation:

public class BinarySearchSolution {
    public int findTarget(int[] data, int targetValue) {
        // Early termination check for out-of-bounds values
        if (targetValue < data[0] || targetValue > data[data.length - 1]) {
            return -1;
        }
        
        int start = 0;
        int end = data.length;
        
        while (start < end) {
            int midpoint = start + (end - start) / 2;
            
            if (data[midpoint] > targetValue) {
                end = midpoint;
            } else if (data[midpoint] < targetValue) {
                start = midpoint + 1;
            } else {
                return midpoint;
            }
        }
        
        return -1;
    }
}

• Time Complexity: O(log n)
• Space Complexiyt: O(1)