计算两个数组中元素的二进制搜索逻辑（GFG）

Question

我正在使用此逻辑在排序数组 b[] 中查找小于或等于 x 的元素。但是，它不适用于某些测试用例。

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

找了一个解决方案后，我发现了下面的逻辑。有人可以告诉我我的逻辑和这个逻辑有什么区别吗？

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

Answer 1

在你的代码中你没有考虑mid+1可以等于b_size，假设b_size=1然后mid=0和mid+1=1，这意味着你正在检查对于索引 1 处的值，即超出数组 b.

范围的 b[1]

计算两个数组中元素的二进制搜索逻辑（GFG）

Binary search logic for Counting elements in two arrays(GFG)

arrays

logic

binary-search