Binary search is a highly efficient algorithm for searching in sorted arrays, but its correct implementation hinges on maintaining consistent loop invariants—specifically, the definition of the search interval. Two common conventions are closed intervals ([left, right]) and half-open intervals ([left, right)). Consistency in choosing and applying one throughout the loop is essential to avoid off-by-one errors.

For a closed interval approach:

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

For a half-open interval ([left, right)):

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

Moving to array manipulation, the problem of removing elements equal to a given value can be approached with brute force, but it leads to O(n²) time complexity due to nested shifting. A more optimal solution uses the two-pointer technique:

class Solution {
    public int removeElement(int[] nums, int val) {
        int writeIndex = 0;
        for (int readIndex = 0; readIndex < nums.length; readIndex++) {
            if (nums[readIndex] != val) {
                nums[writeIndex++] = nums[readIndex];
            }
        }
        return writeIndex;
    }
}

Here, readIndex scans the array, while writeIndex tracks the positoin where the next valid element should be placed. This achieves O(n) time with O(1) space.

A related binary search variant is finding the insertion index for a target in a sorted array when the target may not exist:

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

The key insight is that upon loop termination, left points to the smallest index where nums[left] ≥ target, which is exactly the insretion position.

For finding the first and last positions of a target in a sorted array with duplicates, two modified binary search are used—one to locate the leftmost occurrence and another for the rightmost:

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if (nums.length == 0) return result;

        // Find first position
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                if (mid == 0 || nums[mid - 1] != target) {
                    result[0] = mid;
                    break;
                } else {
                    high = mid - 1;
                }
            }
        }

        // Find last position
        low = 0;
        high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                if (mid == nums.length - 1 || nums[mid + 1] != target) {
                    result[1] = mid;
                    break;
                } else {
                    low = mid + 1;
                }
            }
        }

        return result;
    }
}

In the left-bound search, when nums[mid] == target, we check if it's the first occurrence by verifying the left neighbor. Similarly, for the right bound, we check the right neighbor. This ensures logarithmic time complexity for both searches.