Binary Search Implementation

Given a sorted integer array nums with distinct elements and a target value, the objective is to locate the index of the target. If the target is not present, the function should return -1. Binary search efficiently reduces the search space by half in each iteration, but the implementation must strictly adhere to consistent boundary definitions to avoid errors.

Closed Interval Approach

When the search interval is defined as [low, high], both boundaries are valid indices. The initial high is set to nums.length - 1. The loop condition is low <= high because when low equals high, there is still one element to check. If the middle element is greater than the target, the next high becomes mid - 1 to exclude the middle element from the new range.

public int binarySearchClosed(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

Left-Closed, Right-Open Interval Approach

If the interval is defined as [low, high), the left boundary is inclusive while the right is exclusive. Thus, high initializes to nums.length. The loop condition changes to low < high. Since high is not a valid index, if the middle element is larger than the target, the new high is set to mid, as mid is already excluded from the next search space.

public int binarySearchOpen(int[] nums, int target) {
    int low = 0;
    int high = nums.length;

    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return -1;
}

In-Place Element Removal

This problem requires removing all instances of a specific value val from an integer array nums. The operation must be performed in-place with O(1) extra memory, returning the new length of the modified array. The relative order of elements may be changed, and elements beyond the returned length are irrelevant.

Brute Force Strategy

A nested loop approach provides a straightforward solution. The outer loop iterates through the array, and when a target value is found, the inner loop shifts all subsequent elements one position to the left to overwrite the current index. The array size variable is decremented, and the current index is decremented to re-check the element that was shifted into the current position.

public int bruteForceRemove(int[] nums, int val) {
    int size = nums.length;
    for (int i = 0; i < size; i++) {
        if (nums[i] == val) {
            for (int j = i + 1; j < size; j++) {
                nums[j - 1] = nums[j];
            }
            i--; 
            size--;
        }
    }
    return size;
}

Two-Pointer Technique

The two-pointer method optimizes the process to O(n) time complexity using a single pass. This technique utilizes a fast pointer to scan the array and a slow pointer to mark the position where the next valid element should be written.

• Fast Pointer (src): Iterates through every element in the array.
• Slow Pointer (dest): Only advances when the fast pointer finds an element that is not equal to val, effectively copying valid values to the front of the array.

public int twoPointerRemove(int[] nums, int val) {
    int dest = 0;
    for (int src = 0; src < nums.length; src++) {
        if (nums[src] != val) {
            nums[dest] = nums[src];
            dest++;
        }
    }
    return dest;
}