Binary search using c programming-CodePudding

Given an array of integers which is sorted in ascending order, and an integer target, write a function to search target in the array. If the target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

I solved the above question using the following code:

int search(int* nums, int numsSize, int target){

    int l = 0;
    int r = numsSize -1;
    int result = -1;
    
    while(l <= r)
    {
        int mid = (l   (r-l))/2;
        
        if(nums[mid] == target)
            return result = nums[mid];
        if(nums[mid] < target)
            return l = mid   1;
        else
            return r = mid - 1;
    }
    return result;
}

But I am still not getting the right answer. Please help.

CodePudding user response：

You are returning the newly calculated l and r value.

if(nums[mid] < target)
    return l = mid   1;
else
    return r = mid - 1;

You just need to update them and keep searching the element.

if(nums[mid] < target)
    l = mid   1;
else
    r = mid - 1;

CodePudding user response：

Corrected code:

int search(int* nums, int numsSize, int target){

    int l = 0;
    int r = numsSize -1;
    int result = -1;
    printf("%d %d %d\n", numsSize, target, nums[0]);

    while(l <= r)
    {
        int mid = l   (r - l) / 2;
        
        if(nums[mid] == target)
            return result = mid;
        if(nums[mid] < target)
            l = mid   1;
        else
            r = mid - 1;
    }
    return result;
}

The errors:

You computed wrongly the mid, it's not:

int mid = (l (r-l))/2;

Correct version is:

int mid = l   (r - l) / 2;

You should not use return here because you break the loop.

if(nums[mid] < target)
        return l = mid   1;
    else
        return r = mid - 1;

    if(nums[mid] == target)
          return result = nums[mid];

Here you should return the mid, the position of the target value, not the value itself.