判断一个数是否在区间数组中

Question

我想对间隔数组中的元素执行二进制搜索。例如，我需要在 intervals = [[1,10], [11, 18], [21, 24], [25, 32], [33, 40], [42, 43]] 中找到包含 35 的区间的索引。此外，如果在任何区间内均未找到该数字，则算法需要 return -1。在 python3 上可以吗？我怎样才能修改我的标准二进制搜索功能，使其 return 满足我的需要？这是我的二进制搜索函数的样子：

def b_search(array, element, start, end):
    if start > end:
        return -1
    mid = (start + end) // 2
    if element == array[mid]:
        return mid
    if element < array[mid]:
        return b_search(array, element, start, mid-1)
    else:
        return b_search(array, element, mid+1, end)

提前致谢。

Answer 1

您需要修改二分查找，不再检查元素是否等于mid，而是检查元素是否在中间区间：

def b_search(array, element, start, end):
    if start > end:
        return -1
    mid = (start + end) // 2
    if array[mid][0] <= element <= array[mid][1]:
        return mid
    if element < array[mid][0]:
        return b_search(array, element, start, mid-1)
    return b_search(array, element, mid+1, end)

Answer 2

intervals = [[1,10], [11, 18], [21, 24], [25, 32], [33, 40], [42, 43]]
number = 50
idx_list = [i for i,interval in enumerate(intervals) if interval[0] <= number <= interval[1]]
idx = -1  if not idx_list else idx_list[0]
print(idx)

对于二进制搜索，我们使用以下代码：

def b_search_2d(arr_2d, element, start=0, end=0):
    if end == 0:
        end = len(arr_2d) - 1
    if start > end:
        return -1
    mid = (start + end) // 2
    if arr_2d[mid][0] <= element <= arr_2d[mid][1]:
        return mid
    elif element < arr_2d[mid][0]:
        return b_search_2d(arr_2d, element, start, mid-1)
    else:
        return b_search_2d(arr_2d, element, mid+1, end)       
intervals = [[1,10], [11, 18], [21, 24], [25, 32], [33, 40], [42, 43]]
print(b_search_2d(intervals, 35))
print(b_search_2d(intervals, 50))

判断一个数是否在区间数组中

Determine whether a number is in array of intervals

python

binary-search