Home > front end >  Binary search logic for Counting elements in two arrays(GFG)
Binary search logic for Counting elements in two arrays(GFG)

Time:12-31

I am using this logic to find the element which is less than or equal to x in a sorted array b[]. However, its not working for some of the testcase.

int binary_search(int x, int b[], int b_size)
{
    int low = 0;
    int high = b_size-1;
    
    
    while(low<=high)
    {
        int mid = low   (high-low)/2;
        
        if(b[mid]<=x && b[mid 1]>x) return mid;
        else if(b[mid]>x) high = mid-1;
        else low = mid 1;
    }
}

After looking for a soln, I found the below logic. Can someone please tell me what's the difference between my logic and this one?

int binary_search(int arr[], int l, int h, int x)
{
    while (l <= h) {
        int mid = (l   h) / 2;
 
        // if 'x' is greater than or equal to arr[mid],
        // then search in arr[mid 1...h]
        if (arr[mid] <= x)
            l = mid   1;
 
        // else search in arr[l...mid-1]
        else
            h = mid - 1;
    }
 
    // required index
    return h;
}

CodePudding user response:

In your code you are not considering that mid 1 can be equal to b_size, suppose b_size=1 then mid=0 and mid 1=1, it means you are checking for a value at index 1 i.e. b[1] that is out of bound for array b.

  • Related