二分搜索能否使用while(front != end)作为循环条件？

在二分搜索中，我们通常使用while(front <= end)作为循环条件。现在尝试改用while(front != end)，并在每次循环中检查nums[front]、nums[end]和nums[mid]是否等于目标值，目前测试均返回正确结果，但不确定是否存在失效场景。

给出的代码如下：

class BinarySearch {
public:
    int bin_search(vector<int>& nums, int target) {
        int count = nums.size();
        int front = 0;
        int end = count - 1;

        if(nums[0]==target){return 0;}
        while(front!=end){

            int mid = (end + front)/2;
            // cout<<mid<<endl;
            if(nums[front] == target){return front;}
            else if(nums[end] == target){return end;}


            else if(nums[mid]==target){return mid;}

            else if(nums[mid]<target){
                front = mid+1;
            }

            else if(nums[mid]>target){
                end = mid - 1;
            }
        }

        return -1;
    }
};

有效性分析 #

在数组有序且非空的前提下，这段代码不存在失效场景，原因如下：

• 边界元素全覆盖：开头直接检查了数组首元素nums[0]，每次循环也会优先检查当前front和end指向的元素，确保所有边界位置不会被遗漏；只要目标值存在于数组中，要么会被mid直接命中，要么会在循环的边界检查中被捕获。
• 循环终止无遗漏：当循环终止时front == end，这个位置的元素已经在最后一次循环中被检查过——因为最后一次循环执行时front和end仍不相等，此时会先检查nums[end]（即最终front==end的位置），若目标值是该元素，会直接返回结果，不会走到循环终止后的return -1。

鲁棒性优化建议 #

代码存在一个潜在问题：若输入数组为空，nums[0]会触发数组越界访问，建议在开头增加空数组判断：

if(count == 0) return -1;

内容的提问来源于stack exchange，提问作者Dron Singh