Binary search program cause runtime error and failed hidden test cases

Question

I am practicing binary search with problem 704 on leetcode. At first, I just follow the concept of binary search and came up with this solution:

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;
}

It is not well-designed but it passed all test cases.

After that, I read some articles about binary search, I tried to reimplement it with this piece of code:

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;
}

The problem is it just pass 3/47 test cases and cause runtime error.

So what makes my second version cause error but my first version doesn't.

Any help would be appreciated.

Answer 1

The only thing wrong with your second implementation is using size_t. Change it to int, and it ought to work fine.

size_t is an unsigned type. The value of end can be negative when the search is probing the beginning of the array. This invokes undefined behavior in C. In practice, that usually means the value "underflows" and becomes a huge positive number.

Answer 2

Here is my very short version:

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; 
}