Binary search is a fundamental algorithm that efficiently locates target values in sorted arrays. This article explores several classic LeetCode problems that leverage binary search, along with related array manipulation techniques.

Problem 704: Binary Search

When performing binary search on a sorted array, the choice of boundary conditions significantly impacts the implementation. Two primary approaches exist: closed interval [left, right] and half-open interval [left, right).

Closed Interval Approach

With [left, right] boundaries, the search space includes both endpoints. When the target is smaller than the current element, we move the right boundary to mid - 1 to exclude the current index from future searches. The loop continues until right < left, ensuring we check every remaining element including the last one.

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

Half-Open Interval Approach

Using [left, right) means the right boundary is exclusive. When the target is smaller than arr[mid], we set right = mid (not mid - 1) since the current index is excluded from the next search range. The loop terminates when right == left.

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

Problem 35: Search Insert Position

This problem extends binary search by finding where a target would be inserted to maintain sorted order. Using the closed interval approach, when the target is not found, the loop terminates with left > right. At this point, left represents the exact insertion position because all elements before left are smaller than the target.

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

The key insight is that after the loop exits, left points to the first element greater than or equal to the target, which is precisely the insertion position.

Problem 34: Find First and Last Position of Element in Sorted Array

This problem requires locating the boundaries of all occurrences of a target value. Two distinct solution strategies exist.

Strategy One: Modified Binary Search

First, find any occurrence of the target using standard binary search. Then expand outward in both directions to find the first and last positions. When expanding, it's crucial to verify array bounds before accessing elements to prevent index out of bounds errors.

public int[] findBounds(int[] arr, int target) {
    int[] result = {-1, -1};
    
    int mid = findMid(arr, target);
    if (mid == -1) {
        return result;
    }
    
    // Expand leftward
    int start = mid;
    while (start >= 0 && arr[start] == target) {
        start--;
    }
    
    // Expand rightward
    int end = mid;
    while (end < arr.length && arr[end] == target) {
        end++;
    }
    
    result[0] = start + 1;
    result[1] = end - 1;
    return result;
}

private int findMid(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (right >= left) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

Strategy Two: Boundary-Finding Binary Search

This more sophisticated approach uses specialized binary search variants to directly locate the left and right boundaries.

The solution handles three scenarios:

• Case A: Target lies outside the array bounds (returns [-1, -1])
• Case B: Target is within bounds but not present (returns [-1, -1])
• Case C: Target exists in the array (returns the exact bounds)

public int[] findBounds(int[] arr, int target) {
    int leftBound = getLeftBoundary(arr, target);
    int rightBound = getRightBoundary(arr, target);
    
    // Case A: target outside array range
    if (leftBound == -2 || rightBound == -2) {
        return new int[]{-1, -1};
    }
    
    // Case C: target exists
    if (rightBound - leftBound > 1) {
        return new int[]{leftBound + 1, rightBound - 1};
    }
    
    // Case B: target in range but not found
    return new int[]{-1, -1};
}

private int getRightBoundary(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int boundary = -2;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] > target) {
            right = mid - 1;
        } else {
            // When equal, continue searching right
            left = mid + 1;
            boundary = left;
        }
    }
    return boundary;
}

private int getLeftBoundary(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int boundary = -2;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] >= target) {
            // When equal or greater, continue searching left
            right = mid - 1;
            boundary = right;
        } else {
            left = mid + 1;
        }
    }
    return boundary;
}

The marker value -2 indicates that boundaries were never assigned, signaling the target lies out side the array range.

Problem 27: Remove Element

This problem requires removing all occurrences of a value in-place. Two pointer techniques provide elegant solutions.

Fast-Slow Pointer Technique

Using two pointers tracking different positions in the array, we can build a new array without the target value while maintaining original order.

public int removeElement(int[] arr, int target) {
    int writeIndex = 0;
    int readIndex = 0;
    
    while (readIndex < arr.length) {
        if (arr[readIndex] != target) {
            arr[writeIndex] = arr[readIndex];
            writeIndex++;
        }
        readIndex++;
    }
    return writeIndex;
}

The writeIndex pointer tracks positions for retained elements, while readIndex scans through all elements.

Two-Pointer Swap Technique

This approach uses front and back pointers, swapping elements to efficiently remove target values without preserving relative order.

public int removeElement(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        if (arr[left] == target) {
            // Swap with element at right pointer
            arr[left] = arr[right];
            right--;
        } else {
            left++;
        }
    }
    return left;
}

This method proves more efficient when element order is irrelevant, as it minimizes writes to the array.

Key Takeaways

Understanding boundary conditions in binary search is essential for correct implementations. The choice between closed and half-open intervals affects termination conditions and boundary updates. For array manipulation problems, pointer techniques offer in-place solutions with varying time and space complexities.