算法----二分法找出有序列表指定值

#第一种：先判断在查询
def BinarySearch(arr,key):
    min=0
    max=len(arr)-1
    if key in arr:
        while True:
            center=int((min+max)/2)
            if arr[center]>key:
                max=center-1
            elif arr[center]<key:
                min=center+1
            elif arr[center]==key:
                print(str(key)+"在数组里面的第"+str(center)+"个位置")
                return arr[center]
    else:
        print("没有该数字！")
if __name__=="__main__":
    arr=[1,6,9,15,26,38,49,57,63,77,81,93]
    while True:
        key=input("请输入你要查找的数字:")
        if key== "   ":
            print("谢谢使用！")
            break
        else:
            BinarySearch(arr,int(key))

# 第二种：判断某个元素是否在列表中
#子问题算法（子问题规模为1）
def is_in_list(init_list,e1):
    return [False,True][init_list[0]==e1]
#分治算法
def solve(init_list,e1):
    n=len(init_list)
    if n==1:#若问题规模等于1，直接解决
        return is_in_list(init_list,e1)
    #分解（子问题规模为n/2）
    left_list,right_list=init_list[:n//2],init_list[n//2:]
    #递归（树），分治，合并
    res=solve(left_list,e1) or solve(right_list,e1)
    return res
if __name__=='__main__':
    #测试数据
    test_list=[12,2,23,45,67,3,2,4,45,63,24,23]
    #查找
    print(solve(test_list,45))
    print(solve(test_list,5))

# 第三种：找出有序列表中的指定值
data = [1, 3, 6, 13, 56, 123, 345, 1024, 3223, 6688]


def dichotomy(min, max, d, n):
    """
    min表示有序列表头部索引
    max表示有序列表尾部索引
    d表示有序列表
    n表示需要寻找的元素
    """
    if min > max:  # 终止条件，当查找区间不存在时表示没找到
        return None
    mid = (min + max) // 2  # 整除，确保mid是整数类型索引
    if d[mid] < n:
        print("向右侧找！")
        return dichotomy(mid + 1, max, d, n)  # 更新区间时，mid + 1避免重复检查当前mid位置元素
    elif d[mid] > n:
        print("向左侧找！")
        return dichotomy(min, mid - 1, d, n)  # 同理，mid - 1避免重复检查
    else:
        print('找到了%s' % d[mid])
        return d[mid]  # 返回找到的元素


res = dichotomy(0, len(data) - 1, data, 56)  # 这里max索引应该是len(data) - 1，因为索引从0开始
print(res)

运行结果：

第二种：
 

 

第三种：
 

原文地址：https://blog.csdn.net/qq_68809241/article/details/143819821

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！