1. 题目🔍

本题要求采用折半查找的思想，每次搜索原来数据的一半，直到搜索成功或待搜索数据为空。

1.1 输入格式

输入一个列表A和查找的值B。

1.2 输出格式

如果查找成功输出数B在列表A中的位置，否则输出查找不成功。

1.3 输入样例1

[19,23,46,49,65,78,98,101,125]
46

1.4 输出样例1

46 2

1.5 输入样例2

[19,23,46,49,65,78,98,101,125]
82

1.6 输出样例2

not find

2. 题解✨

2.1 思路

使用eval()将输入的值转化为列表，使用sorted()将列表排序

关键 创建一个折半查找的函数，传入值为列表A与数字B

折半查找判断方法：

将列表中间位置的值与查找值比较

• 如果两者相等，则查找成功；否则，利用中间位置的值将表分成前、后两个子列表，
• 如果中间位置记录的值大于查找值，则进一步查找前一子列表；
• 如果中间位置记录的值小于查找值，则进一步查找后一子列表。

---

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

2.2 代码

a = sorted(eval(input()))		# 将输入转化为列表，并排序
b = int(input())


def find(ls, item):
    low = 0
    high = len(ls)
    while low < high:
        mid = int((low + high)/2)
        temp = ls[mid]
        if temp == item:
            return mid
        elif temp > item:
            high = mid - 1
        else:
            low = mid + 1
    return False


if find(a, b) is False:
    print('not find')
else:
    print('{} {}'.format(b, find(a, b)))

相关内容

• Python期末考试总复习资料

折半查找

“”"
0 1 2 3 4 5 6 7 8 9
list = [11,22,33,44,55,66,77,88,99,111]
假设需要：66
第一次：（0+9）//2 = 4 ；55和66比较
接下来55的右边找：66,77,88,99,111
第二次：（5+9）//2 = 7 ； 88和66比较
接下来在88左边找，66,77
第三个：（5+6）//2 = 5 ； 66==66，下标对应5
开始下标：0开始，慢慢变大 5 6
结尾下标：（个数 - 1） 慢慢减小 6 5

“”"

list = [11,22,33,44,55,66,77,88,99,110]
n = int(input("输入需要查找的值："))
start = 0 #最左边开始下标
end = len(list)-1 #最右边开始的下标
index = -1 #对应的下标 -1没有找到
while start <= end :
    #中间值与n进行比较
    mid = (start+end)//2
    if list[mid] == n: #数值被找到
        index = mid
        break
    elif list[mid] < n: ##继续 在中间值的右边查找
        start = mid + 1
    else:
        end = mid -1
print("%d 对应下标：%d"%(n,index))

# -*- coding:utf8 -*-
def bin_search(items, key):
    '''折半查找'''
    start, end = 0, len(items) - 1
    while start <= end:
        mid = (start + end) // 2
        if key > items[mid]:
            start = mid + 1
        elif key < items[mid]:
            end = mid - 1
        else:
            return mid

    return -1

print(bin_search([3.2,2,10,3,1,45,90,0], 3))