Binary Search in a Sorted Array

Given a sorted array arr of n integers in ascending order and a target value target, implement a function to search for target within arr. Return the index if found; otherwise, return -1. The array contains no duplicate elements.

Example 1:

Input: arr = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Example 2:

Input: arr = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Binary search operates by repeated dividing the search interval in half. The choice of interval boundaries—whether inclusive or exclusive—affects the loop condition and index updates.

Closed Interval Approach [left, right]

The interval includes both endpoints. Initialize left = 0 and right = arr.size() - 1. The loop continues while left <= right because a single-element interval is valid. Calculate the midpoint as mid = left + (right - left) / 2 to prevent potential integer overflow.

• If arr[mid] > target, the target lies in the left half. Udpate right = mid - 1 to exclude the already checked mid.
• If arr[mid] < target, the target is in the right half. Update left = mid + 1.
• If arr[mid] == target, return mid.

If the loop exits without finding the target, return -1.

int binarySearchClosed(vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    while (low <= high) {
        int center = low + (high - low) / 2;
        if (arr[center] > target) {
            high = center - 1;
        } else if (arr[center] < target) {
            low = center + 1;
        } else {
            return center;
        }
    }
    return -1;
}

Half-Open Interval Approach [left, right)

The interval includes left but excludes right. Initialize left = 0 and right = arr.size(). The loop condition is left < right because when left == right, the interval is empty. The midpoint calculation remains the same.

• If arr[mid] > target, update right = mid. The new interval is [left, mid).
• If arr[mid] < target, update left = mid + 1. The new interval is [mid + 1, right).
• If arr[mid] == target, return mid.

int binarySearchHalfOpen(vector<int>& arr, int target) {
    int start = 0;
    int end = arr.size();
    while (start < end) {
        int pivot = start + (end - start) / 2;
        if (arr[pivot] > target) {
            end = pivot;
        } else if (arr[pivot] < target) {
            start = pivot + 1;
        } else {
            return pivot;
        }
    }
    return -1;
}

Removing Elements In-Place from an Array

Given an array data and a value key, remove all occurrences of key from data in-place. The relative order of the remaining elements may change. Return the count k of elements not equal to key. The first k elements of data should hold these remaining elements; the contents beyond index k are irrelevant.

Example 1:

Input: data = [3, 2, 2, 3], key = 3
Output: 2, data = [2, 2, _, _]

Example 2:

Input: data = [0, 1, 2, 2, 3, 0, 4, 2], key = 2
Output: 5, data = [0, 1, 4, 0, 3, _, _, _]

Brute-Force Solution

A straightforward method uses nested loops. The outer loop iterates through the array. When an element matching key is found, an inner loop shifts all subsequent elements one position left to fill the gap. The array size and current index are adjusted accordingly.

int removeElementBrute(vector<int>& data, int key) {
    int length = data.size();
    for (int i = 0; i < length; ++i) {
        if (data[i] == key) {
            for (int j = i + 1; j < length; ++j) {
                data[j - 1] = data[j];
            }
            --i; // Re-check the current index after shift
            --length; // Reduce effective size
        }
    }
    return length;
}

This approach has a time complexity of O(n²) due to the shifting operation.