mongona

mongona
-- --
正在获取天气

二分查找(非递归、递归)python实现

# -*- coding: utf-8 -*-
"""
@author: sato
@file: binary_search.py
@time: 2019-09-03 15:21

"""


def binary_search(array, key):
    """二分查找非递归"""
    if len(array) <= 1:
        if array[0] != key:
            return
    start = 0
    end = len(array) - 1
    while start <= end:
        mid = (end + start) // 2
        if key < array[mid]:
            end = mid - 1
        elif key > array[mid]:
            start = mid + 1
        else:
            return True


def binary_search_reduce(array, key):
    """二分查找,递归实现版本"""
    if len(array) == 0:
        return False
    mid = len(array) // 2
    if array[mid] == key:
        return True
    elif key < array[mid]:
        return binary_search_reduce(array[:mid], key)
    else:
        return binary_search_reduce(array[mid + 1:], key)


if __name__ == '__main__':
    # 二分查找的最优时间复杂度为O(1),最坏时间复杂度为O(log n)
    # 递归空间复杂度是:O(N)  非递归: O(1)
    # 使用场景: 在有序数组中寻找指定元素
    sorted_list = [1, 4, 5, 7, 8, 9, 10, 13, 15, 17, 19, 23, 35]
    assert binary_search(sorted_list, 1)
    assert binary_search(sorted_list, 10)
    assert binary_search(sorted_list, 35)
    assert binary_search_reduce(sorted_list, 1)
    assert binary_search_reduce(sorted_list, 13)
    assert binary_search_reduce(sorted_list, 35)

 

3
2
Tags
富强,民主,文明,和谐,自由,平等,公正,法治,爱国,敬业,诚信,友善。
打赏二维码
About
Sato
毕竟,代码只是思想的一种体现而已!!! 架构师就像军师,不是对面啥阵势都用大军队来干,小阵势小技术,小公司不必要也不用引入分布式
Category
Tags
Site statistics

本站现有文章24篇,共被浏览13579

本次响应耗时: 0.490s

当前来路IP: 18.207.136.184  美国

您是本站第: 15398 位访客!

本站已苟活: 

All hots
Article archiving