欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python实现二分查找算法

程序员文章站 2024-03-19 15:28:04
...

二分查找算法

        二分算法是一种效率比较高的查找算法,其输入的是一个有序的元素列表,如果查找元素包含在列表中,二分查找返回其位置,否则返回NONE
        想象一个场景:
        我随便想1~100中的数字,你的目标是以最少的次数猜中我所想的数字,那么你会怎么做呢?

  • 你可能会从1开始以此往上猜,直到猜中数字,这是一种简单查找算法,每次猜测只能排除一个数字
  • 你可能从50开始猜,我告诉你大了或者小了,这样每猜一次,都会将剩余的数字排除掉一半,不管我心里想的是哪个数字,你在7次之内都能够猜到,因为每次猜测都将排除很多数字!

相比之下,第二种方法会更加省时,这种算法叫做二分算法,又称折半查找。

对于要搜索的元素越多,二分查找速度比简单查找快的更多 这是二分查找算法的优点,但二分算法也有缺点,二分算法只针对有序的列表,这样插入和删除就会很困难,因此,折半查找方法只适合不经常变动的有序列表

Python实现二分算法

# 二分算法是一种高效的查找算法,针对有序的数列


def binary_search(my_list, num):
    """
    二分算法
    :param my_list: 有序列表
    :param num: 要查找的元素
    :return: 存在返回下标 不存在返回NONE
    """
    low = 0
    high = len(my_list) - 1

    while low <= high:
        mid = int((low + high) / 2)
        guess = my_list[mid]

        if guess == num:
            return mid
        elif guess > num:
            # 说明猜大了
            high = mid - 1
        else:
            low = mid + 1

    return None


def main():
    """主函数"""
    my_list = [1, 3, 5, 7, 9]  # 有序列表
    num = 2  # 要猜测的数字
    print(binary_search(my_list, num))


if __name__ == '__main__':
    main()

返回num下标 1
二分查找算法运行时间:O(log2 n )
简单查找算法运行时间:O(n)

相关标签: 二分算法