Binary Search (LeetCode 704)

Binary search requires the input array to be sorted and typically contains unique elements to ensure the result is unambiguous. The algorithm reduces the search space by comparing the target with the middle element of the currrent interval.

Approach 1: Closed Interval [left, right]

In this approach, left and right represent the actual first and last indices. Since the interval is inclusive, the loop continues as long as left <= right.

class Solution {
public:
    int search(vector<int>& arr, int key) {
        int start = 0;
        int end = arr.size() - 1;

        while (start <= end) {
            // Calculate mid to avoid potential overflow from (start + end)
            int mid = start + (end - start) / 2;

            if (arr[mid] > key) {
                end = mid - 1; // Target is in the left half
            } else if (arr[mid] < key) {
                start = mid + 1; // Target is in the right half
            } else {
                return mid; // Target found
            }
        }
        return -1; // Target not found
    }
};

Approach 2: Half-Open Interval [left, right)

Here, right represents the index just past the last element. Consequently, left == right is a invalid empty range, so the loop condition is left < right.

class Solution {
public:
    int search(vector<int>& arr, int key) {
        int start = 0;
        int end = arr.size(); 

        while (start < end) {
            int mid = start + ((end - start) >> 1); // Using right shift for division by 2

            if (arr[mid] > key) {
                end = mid; // Narrow down to [start, mid)
            } else if (arr[mid] < key) {
                start = mid + 1; // Narrow down to [mid + 1, end)
            } else {
                return mid;
            }
        }
        return -1;
    }
};

Remove Element (LeetCode 27)

Brute Force

A naive solution involves two nested loops. When the target value is found, shift all subsequent elements forward. This results in a time complexity of $O(n^2)$.

Optimized Approach: Two Pointers

Single Direction (Slow/Fast)

This method maintains the relative order of elements. The fast pointer explores the array, while the slow pointer writes valid elements.

class Solution {
public:
    int removeElement(vector<int>& data, int target) {
        int writeIdx = 0;
        for (int readIdx = 0; readIdx < data.size(); ++readIdx) {
            if (data[readIdx] != target) {
                data[writeIdx] = data[readIdx];
                ++writeIdx;
            }
        }
        return writeIdx;
    }
};

Opposing Directions

This approach swaps elements to minimize movements. It is efficient when the number of elements to remove is small, though it changes the original order.

class Solution {
public:
    int removeElement(vector<int>& data, int target) {
        int front = 0;
        int back = data.size() - 1;

        while (front <= back) {
            // Advance front until we find the target value
            while (front <= back && data[front] != target) {
                ++front;
            }
            // Move back until we find a non-target value
            while (front <= back && data[back] == target) {
                --back;
            }
            // Swap or overwrite
            if (front < back) {
                data[front] = data[back];
                ++front;
                --back;
            }
        }
        return front;
    }
};

Complexity Reference

When evaluating algorithm efficeincy, common time complexities rank as follows: $O(\log n) < O(n) < O(n \log n) < O(n^2)$. Solutions often return the result directly to the caller without standard input/output handling in the function itself.