Python实现二分法查找(binary search)

对于从小到大有序排列的元素组合,使用二分法查找(binary search)是一种效率较高的算法,其大致流程如下:

  1. 将要查找的元素x与中间元素进行比较;
  2. 如果x与中间元素匹配,则返回中间元素的索引;
  3. 如果x大于中间元素,则取中间元素之后的部分,并使用这部分从第一步开始查找x;
  4. 如果x小于中间元素,则取中间元素之前的部分,并使用这部分从第一步开始查找x;

使用递归实现

def binary_search(arr, low, high, x):
    
    if high < low: return -1 
 
    mid = (high + low) // 2
    
    if arr[mid] == x:
        # 找到元素返回中间索引
        return mid
 
    # If element is smaller than mid, then it can only
    # be present in left subarray
    elif arr[mid] > x:
        # x < 中间元素,取中间元素左边的部分进行查找
        return binary_search(arr, low, mid - 1, x)
    else:
        return binary_search(arr, mid + 1, high, x)

#测试数据,必须是从小到大的有序元素
arr = [ 1 , 4 , 6 , 7 , 11 , 19 ]

x = 19

result = binary_search(arr, 0, len(arr)-1, x)
 
if result != -1:
    print("元素的索引为:", str(result))
else:
    print("没有找到元素!")

输出:

元素的索引为: 5

使用迭代的方式实现

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
 
        mid = (high + low) // 2
 
        if arr[mid] < x:
            low = mid + 1
 
        elif arr[mid] > x:
            high = mid - 1
 
        else:
            return mid
 
    return -1
 
 
arr = [ 1 , 4 , 6 , 7 , 11 , 19 ]
x = 19

result = binary_search(arr, x)
 
if result != -1:
    print("元素的索引为:", str(result))
else:
    print("没有找到元素!")

原创内容,如需转载,请注明出处;

本文地址: https://www.perfcode.com/p/binary-search-in-python.html

分类: 计算机技术
推荐阅读:
Golang实现字符串的SHA1加密 本文将使用Go语言内置包 crypto/sha1 来实现SHA1加密。
pip和pip3有什么区别,用哪个? pip 是一个现代的,通用的 Python 包管理工具。提供了对 Python 包的查找、下载、安装、卸载的功能。
Python实现臭皮匠算法(Stooge Sort) 臭皮匠排序(Stooge Sort)是一种递归排序算法,是一种比较低效率的排序算法;
Python max()函数 max() 是 Python 中的一个内置函数,用于返回给定可迭代对象中的最大值。
Python 使用tld库获取复杂URL的顶级域名 我们会碰到各种各样的URL链接,比如:www.a.com/ b.com.cn/ a.b.c.com.cn a.com/b.com Python有内置的库可以识别一些简单的URL,但是像a.b.c.com.cn这样却无能为力。我们需要一个强大的第三方库来实现提取顶级域名。
C语言islower()函数:判断字符是否为小写字母 islower()是C语言标准库中的一个函数,用于检查一个字符是否为小写字符;如果传入的字符参数是小写字母,则返回非0值,否则返回0;