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

分类: 计算机技术
推荐阅读:
PySide6 动态创建按钮数组 动态创建按钮数组在许多场合非常有用,特别是当你需要根据用户输入、数据量或其它条件来生成界面元素时;本片将演示如何使用PySide6来动态的创建按钮数组,并正确响应对应按钮的点击信号;
Python 列表(List)的详细用法 列表(list)按特定顺序存储一系列项目。你可以使用索引或在循环中访问项。本问讲述了Python中列表的增加、修改、删除、遍历、复制等基本操作。
Python dict()函数 在Python中,dict()函数用于创建一个字典对象。它可以接受不同类型的参数,并根据参数的不同生成字典对象。具体来说,dict()函数有以下三种使用方式:
使用Python向Bing Webmaster Tools提交URL 在本文中将使用Python向Bing Webmaster Tools提交URL,提交的URL会被很快进行评估,满足质量标准时,就会出现在bing搜索结果中;
Rust字符串转换成数字类型:简单易懂的教程 在Rust编程中,将字符串转换为数字类型是一个常见的任务。无论您是处理用户输入,读取文件,还是与外部API交互,都可能需要将字符串转换为数字以进行进一步的计算或处理。在本文中,我们将深入探讨如何在Rust中执行这一任务,提供简单易懂的教程和示例代码。
Python divmod()函数 在Python中,divmod()函数是一个内置函数,用于将两个数字相除并返回商和余数。divmod()函数接受两个参数,分别是被除数和除数,并返回一个包含商和余数的元组。其中,商是两个数相除得到的结果,而余数是两个数相除后的余数部分。