马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 yexing 于 2020-3-7 20:30 编辑
什么是二分查找？
来源百度百科
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
听了概念，感觉好乱啊
不慌，举个例子你就明白了。
假设你和你的朋友正在玩猜数字的游戏，朋友来猜：
你：猜一个 1 到 10 的数字。（答案4）
这时你的朋友用一种比较“傻”的方法来猜。
朋友：1
你：小了
朋友：2
你：小了
朋友：3
你：小了
朋友：4
你：对了。
朋友猜了4次就对，但是，如果范围是1到100，答案是99，那么朋友不就得猜99次了吗？
这时，二分查找登场了：
你：猜一个 1 到 10 的数字。（答案4）
朋友：5
你：大了
朋友：3
你：小了
朋友：4
你：对了。
别看只比上次少猜了1次，如果范围是1到100，只需要猜6到7次！
好的，了解完二分查找，是时候上 Python 代码了。def binary_search(lst, item):
"""
lst: 一个有序序列（注意一定是有序序列）
item: 目标元素
return: 如果元素在序列中则返回索引值，否则返回None
"""
low = 0
high = len(lst)-1
while low <= high:
index = (low + high) // 2
guess = lst[index]
if guess == item:
return index
if guess > item:
high = index - 1
else:
low = index + 1
return None
>>> my_list = [1, 3, 5, 7, 9]
>>> print(binary_search(my_list, 3))
1
>>>
首先确定第一次查找的范围，即0到序列的最后一个索引值。
然后看第10行，就是取范围内的数的中间值（即“分界线”）。
然后就进入循环，如果猜的数比目标元素小了或大了，就执行第14行或第16行的代码内容，修改 low 和 high 的值，即修改猜的范围。
如果猜的数等于目标元素，那么就返回索引值。
利用二分查找思想，我写了个小程序，让Python用二分查找思想来猜我们给的一个范围内的数字（是不是似曾相识，Python教程的第一个小游戏就是让我们猜 random 模块给的随机数，那么这次我们让 Python 来猜我们给的答案 ）def binary_search(ls, answer):
low = 0
high = len(ls) - 1
count = 0
print("Python正在努力猜数字中...")
while low <= high:
count += 1
guess_index = (low + high) // 2
guess_value = ls[guess_index]
if guess_value == answer:
break
if guess_value < answer:
high = guess_index - 1
else:
low = guess_index + 1
print(f"Python猜对啦！它猜了{count}次。")
def main():
start = int(input("请输入开始的数: "))
end = int(input("请输入结束的数: "))
answer = int(input("请输入答案: "))
while not(answer >= start and answer <= end):
answer = int(input(f"你输入的数没有在{start}和{end}之间！请重新输入: "))
ls = [i for i in range(start, end+1)] #生成一个列表，存放猜的范围内的数
binary_search(ls, answer)
if __name__ == "__main__":
main()
这样，Python猜数字的思维又更加“人类化”了。
其实上面的代码主要还是用了二分查找的示例代码，然后套了层皮而已。
以前我还写了一个用 random 随机数来猜我们给的答案的小游戏（黑历史 ），这个程序是完全随机的，也就是要猜很多次，相比起来肯定是二分查找思想更人性化。
当然，仅仅使用二分查找来模拟人类思维肯定是不够的，更多算法我还在学习中
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2020-3-7 17:41:48
置顶卡
千斤顶
显身卡
楼主
发表于 2020-3-7 17:52:17