二进制搜索程序导致运行时错误和失败的隐藏测试用例

Question

我正在用 problem 704 on leetcode 练习二进制搜索。起初，我只是遵循二进制搜索的概念并想出了这个解决方案：

int search(int* nums, int numsSize, int target){
    size_t start=0, end=numsSize-1;
    while(start!=end){  // if start == end then break
        if(nums[(start+end)/2] > target){
            end=(start+end)/2;
        }
        else if(nums[(start+end)/2] < target){
            start=(start+end)/2+1;
        }
        else{
            return (start+end)/2;
        }
    }        
    if(nums[start]==target){    // when start == end
        return start;
    }       
    return -1;
}

它的设计不是很好，但它通过了所有测试用例。

之后看了一些二分查找的文章，尝试用这段代码重新实现：

int search(int* nums, int numsSize, int target){
    size_t start=0, end=numsSize-1;
    while(start<=end){
        size_t mid = (start+end)/2;
        if(nums[mid]==target){
            return mid;
        }
        else if(nums[mid] > target){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }
    return -1;
}

问题是它只通过了 3/47 个测试用例并导致运行时错误。

为什么我的第二个版本会出错，而我的第一个版本却不会。

如有任何帮助，我们将不胜感激。

Answer 1

你的第二个实现唯一的错误是使用 size_t。将其更改为 int，它应该可以正常工作。

size_t 是无符号类型。当搜索探测数组的开头时，end 的值可以为负。这会调用 C 中的未定义行为。实际上，这通常意味着值“下溢”并变成一个巨大的正数。

Answer 2

这是我的非常简短的版本：

int search(int* nums, int numsSize, int target){
    int lo=0;
    int hi=numsSize-1;
    
    int* x[]= {&lo, &hi};
    while(hi-lo>1)
    {
        int mid=lo+(hi-lo)/2;
        if (nums[mid]==target) return mid;
        *x[nums[mid]>target] = mid;
    }
    
    return (nums[lo]==target)? lo:
           (nums[hi]==target)? hi: -1; 
}

二进制搜索程序导致运行时错误和失败的隐藏测试用例

Binary search program cause runtime error and failed hidden test cases

c

arrays

binary-search