中国股市比赌场还不如 -- 因为在中国股市,某些人可以看别人的底牌@吴敬琏

二分查找算法的 Python 实现

Python 2018-05-19 浏览量: 336 字数统计: 235 最后更新: 2018-05-19 11:39

本来查找列表里面的 一个值的下标,我们可以直接index,例如

list_one = [1, 3, 5, 7, 9, 13, 18, 26, 29, 79]
print(list_one.index(13))

>>> 5

而有时候会抽风非要自己实现一个查找
下面是一个实现的过程

list_one = [1, 3, 5, 7, 9, 13, 18, 26, 29, 79]


def find(list, value):
    middle = len(list) // 2
    if list[middle] < value:
        list_tow = list[middle:]
        find(list_tow, value)
    elif list[middle] > value:
        list_tow = list[:middle]
        find(list_tow, value)
    else:
        print(list[middle])


find(list_one, 13)

上面的例子 只是实现了二分找到这个值,并不能准确的写出index
因为每次,都会截取成一个新的list,所以没有办法确定最原始的那个list 里面的index

所以改进一下 不改变原始的list,也就是不去切片得到一个新的list,从而可以在原始的list 找到index。

list_one = [1, 3, 5, 7, 9, 13, 18, 26, 29, 79]


def find(list, value, start=0, end=None):
    end = len(list) if end is None else end
    middle = (end - start) // 2 + start
    if start <= end:
        if list[middle] > value:
            result = find(list, value, start=start, end=middle - 1)
            return result
        elif list[middle] < value:
            result = find(list, value, start=middle + 1, end=end)
            return result
        else:
            return list[middle], middle
    else:
        return 'not have the num'


print(find(list_one, 13))

递归是,停在当前位置,再去调用自己,所以第二次调用返回的结果会给第一次调用

所以如果上面的 代码,

result = find(list, value, start=start, end=middle - 1)
            return result

# 如果 直接就是  find(list, value, start=start, end=middle - 1)
的话,就会在最后一次调用 return的 值的时候返回给上一次调用,但是上一次调用并没有返回值,所以最后的结果会是 None

def find(list, value, start=0, end=None):
    end = len(list) if end is None else end
    middle = (end - start) // 2 + start
    if start <= end:
        if list[middle] > value:
            find(list, value, start=start, end=middle - 1)
        elif list[middle] < value:
            find(list, value, start=middle + 1, end=end)
        else:
            return list[middle], middle
    else:
        return 'not have the num'

print(find(list_one, 13))

>>> None
小蜗牛 说:
Freedom is the source from which all meaning and all values spring .


文章版权归 原文作者所有丨本站默认采用CC-BY-NC-SA 4.0协议进行授权| 转载必须包含本声明,并以超链接形式注明原文作者和本文原始地址: https://www.tougetu.com/2018/05/dichotomy-python.html

只有地板了

  1. ???
    sample = list_one.copy()
    sample.append(98)
    
    for index in range(len(sample)):
        assert index == find(list_one, sample[index])[1]

    Boom(╯‵□′)╯炸弹!•••*~●?

添加新评论

代码 Pastebin Gist 加粗 删除线 斜体 链接 签到