python – 使用二进制搜索获取最接近值的索引

发布时间：2020-12-20 12:06:28 所属栏目：Python 来源：网络整理

导读：我想在 python中进行二进制搜索： def binarySearch(data,val): 其中data是排序数组,value是要搜索的值.如果找到该值,我想返回索引(这样数据[index] = val).如果找不到该值,我想返回最接近该值的项的索引. 这是我得到的： def binarySearch(data,val): high

我想在 python中进行二进制搜索：

def binarySearch(data,val):

其中data是排序数组,value是要搜索的值.如果找到该值,我想返回索引(这样数据[index] = val).如果找不到该值,我想返回最接近该值的项的索引.

这是我得到的：

def binarySearch(data,val):
    high = len(data)-1
    low = 0
    while True:
        index = (high + low) / 2
        if data[index] == val:
            return index
        if data[index] < val:
            low = index
        if data[index] > val:
            high = index

解决方法

这样的事情应该有效.它返回一个包含两个索引的数组.如果找到val,则返回数组中的两个值都相同.否则,它返回最接近val的两个项的索引.

def binarySearch(data,val):
    highIndex = len(data)-1
    lowIndex = 0
    while highIndex > lowIndex:
            index = (highIndex + lowIndex) / 2
            sub = data[index]
            if data[lowIndex] == val:
                    return [lowIndex,lowIndex]
            elif sub == val:
                    return [index,index]
            elif data[highIndex] == val:
                    return [highIndex,highIndex]
            elif sub > val:
                    if highIndex == index:
                            return sorted([highIndex,lowIndex])
                    highIndex = index
            else:
                    if lowIndex == index:
                            return sorted([highIndex,lowIndex])
                    lowIndex = index
    return sorted([highIndex,lowIndex])

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!