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

二分查找的Python实现细节

程序员文章站 2024-03-19 21:27:28
...

为节约时间,实现细节与注意事项均放入代码注释行中了

# 二分查找(binary search):
# 若需要猜测1-100之间的一个数,可使用二分法(循环查找效率过低):
  # 1、让每个问题的答案将可能的范围减半
  # 2、首先问“是否大于50?”
  # 3、若是,则继续问“是否大于75?”,以此类推
  # 4、注意,备查序列必须是有序结构,关键字按大小排列

def binary_search(list, target):
    '''
    :param list:
    :param target:
    :return:返回待查元素的索引位置,若无则返回提示语句
    '''
    low_line=0
    high_line=len(list)-1
    index=1

    while low_line<=high_line:
        mid=(low_line+high_line)//2

        if list[mid]==target:
            return f'一共查找了{index}次,目标值在列表中的索引位置为{mid}'

        elif list[mid]>target:
            high_line=mid-1

        elif list[mid]<target:
            low_line=mid+1

        index+=1
    return f'该目标值不存在,一共查找了{index}次。'

if __name__ == '__main__':

    L1=list(range(10))
    result1=binary_search(L1,10)
    print(result1)

    L2=[1,2,3,4,5]
    result2=binary_search(L2,5)
    print(result2)

# 自然语言描述:

# 一、前置条件:
# 1、首先明确目标为使用二分法快速查找目标值在列表中的索引位置(即下标)
# 2、定义函数名称,并指定所需变量,list就是待查找列表,target就是目标值
# 3、为使用二分法,需设置下标上下限、下标中间值、循环结构、判断结构
# 4、为获知查找次数,需设一个初始值为1、并随循环次数增加的变量值index

# 二、编写细节:
# 1、将下标的初始下限设为0,初始上限设为列表长度减一
  # (因为列表的索引下标是从0开始,最后一位恰好等于长度减一)
# 2、使用while循环,只要下限大于上限就终止循环执行(以免下标越界导致崩溃)
# 3、在while循环内的第一行设置mid初始值及变化公式,以供每次循环时使用
# 4、上限与下限之和除以二(相当于将查找区间对折),即为中间值,
  # 为避免出现小数,应使用//地板除(将结果向下取整数)
# 5、开始逻辑判断:
  # 以mid变量中存储的当前中间值为索引下标,通过list[mid]获取对应位置的列表值
  # 首先判断对应列表值与目标值是否相等,若相等则返回mid变量中存储的当前下标
  # 若对应列表值大于目标值,则对折搜索区间,将上限重设为mid-1(就是上一个中间值的左侧)
  # 若对应列表值小于目标值,则对折搜索区间,将下限重设为mid+1(就是上一个中间值的右侧)
# 6、每循环一次,就让index=index+1,从而获取循环次数
# 7、若循环结束(即下限大于上限后)始终未能找到,则返回提示语句。

# 三、调用函数时需注意的细节:
# 1、注意,range函数的返回值的类型并不是列表,而是<class 'range'>,
  # 因此需要用list函数将其转化为列表。
# 2、range函数生成的是一个左闭右开的等差序列,range(10)就是0~9,不包括10