数组元素的原地移除策略

在处理类似 LeetCode 27 号题目时，核心任务是剔除指定值并返回新的有效长度。由于编程语言中的数组通常是定长结构，所谓的"移除"实际上是通过后续数据前移覆盖目标值，从而压缩逻辑上的数组容量。

方案一：常规遍历覆盖

最直观的思路是遍历每一个位置，一旦发现匹配目标值的元素，就将其后面的所有元素依次向前移动一位。这种方法的时间复杂度较高，但在理解数组内存移动方面具有教学意义。

class Solution {
    public int removeItem(int[] arr, int targetVal) {
        int currentSize = arr.length;
        
        for (int i = 0; i < currentSize; ) {
            if (arr[i] == targetVal) {
                // 发生位移操作
                for (int k = i; k < currentSize - 1; k++) {
                    arr[k] = arr[k + 1];
                }
                // 索引回退以便重新检查当前位置的新元素
                i--; 
                currentSize--;
            } else {
                // 仅当不匹配时才前进
                i++;
            }
        }
        return currentSize;
    }
}

注意：循环条件必须基于动态变化的数组长度，否则可能引发越界或无效迭代。此外，若发现待移除元素，指针需要回退以确保新移入的值被正确校验。

方案二：快慢指针协同（推荐）

为了将时间复杂度降低至线性级别，可以采用双指针技术。定义一个读取指针扫描原数据，一个写入指针记录保留数据的位置。读取指针负责筛选合法值，写入指针负责紧凑排列。

public class Solution {
    public int compactArray(int[] data, int valueToRemove) {
        int writeIdx = 0;
        int totalLen = data.length;
        
        for (int readIdx = 0; readIdx < totalLen; readIdx++) {
            // 跳过目标值，仅复制非目标值
            if (data[readIdx] != valueToRemove) {
                data[writeIdx++] = data[readIdx];
            }
        }
        return writeIdx;
    }
}

该方法只需遍历一次数组，空间复杂度为常数级，是解决此类问题的标准范式。

二分查找的区间边界处理

二分检索的核心在于每次迭代将搜索范围缩小一半。实现的关键难点在于维护循环不变量，即明确区间的开闭状态，这直接决定了终止条件和边界更新逻辑。

模式 A：闭区间 [left, right]

在此模式下，左右边界均包含在内。循环继续的条件是左边界小于等于右边界。当计算出的中点不符合目标时，需根据比较结果调整边界。

class BinarySearcher {
    public int findTarget(int[] list, int goal) {
        int l = 0;
        int r = list.length - 1; // 初始化为最后一个有效索引
        
        while (l <= r) {
            int mid = l + (r - l) / 2;
            
            if (list[mid] == goal) {
                return mid;
            } else if (list[mid] < goal) {
                // 目标在右半部分，排除当前中点
                l = mid + 1;
            } else {
                // 目标在左半部分，排除当前中点
                r = mid - 1;
            }
        }
        return -1;
    }
}

模式 B：半开区间 [left, right)

这种写法常见于 C++ STL 风格或特定语言库中。右边界代表不包含该索引，因此初始右值为数组长度。循环条件变为严格小于。当右侧边界收缩时，直接赋值给中点即可。

class BinarySearcherOpen {
    public int locateIndex(int[] sequence, int query) {
        int left = 0;
        int right = sequence.length; // 右边界不可达
        
        while (left < right) {
            int pivot = left + (right - left) / 2;
            
            if (sequence[pivot] == query) {
                return pivot;
            } else if (sequence[pivot] < query) {
                // 搜索范围变为 [pivot+1, right)
                left = pivot + 1;
            } else {
                // 搜索范围变为 [left, pivot)，pivot 本身被排除
                right = pivot;
            }
        }
        return -1;
    }
}

两种实现最终都能达成目的，关键在于开发者需始终保持对循环终止状态的清晰认知，避免死循环或索引越界。