03月21, 2019

二分查找

不知道你们曾经是否看过《幸运52》,里面有个经典的游戏是猜价格,一定时间内猜对就可以拿走。参与者每次报一个加钱,李咏只告诉他报高了还是报低了。不少人都是每次随便上调、下调一下报价,现在想想,如果直接用二分查找的方法,很快就能猜到价格了。什么是二分查找呢,在有序的数组中查找某个元素是否存在。以幸运52猜价格的环节为例,假如让我们猜一个冰箱(3850元)的价格,通常的冰箱顶多5000块钱吧,我们就先给李咏报价2500,看是在[0, 2500)还是[2500, 5000)

  • 2500
  • 李咏:低了
  • 这个时候我们知道价格在[2500, 5000)之间了
  • 再把[2500, 5000)这个区间分成两份:[2500, 3750)和[3750, 5000),报价3750
  • 李咏:低了
  • [3750, 4375)和[4375, 5000) 报价4375
  • 李咏:高了
  • [3750, 4062)和[4062, 4375) 报价4062
  • 李咏:高了
  • [3750, 3906)和[3906, 4062) 报价3906
  • 李咏:高了
  • [3750, 3828)和[3828, 3906) 报价3828
  • 李咏:低了
  • [3828, 3867)和[3867, 3906) 报价3867
  • 李咏:高了
  • [3828, 3847)和[3847, 3906) 报价3847
  • 李咏:低了
  • [3847, 3876)和[3876, 3906) 报价3876
  • 李咏:高了
  • [3847, 3861)和[3861, 3876) 报价3861
  • 李咏:高了
  • [3847, 3854)和[3854, 3861) 报价3854
  • 李咏:高了
  • [3847, 3850)和[3850, 3854) 报价3850
  • 李咏:恭喜你!这台冰箱属于你了!

python实现:

def binary_search(search_list, target):
 left = 0
 right = len(search_list) - 1
 while left <= right:
     mid = (left + right) / 2
     if search_list[mid] < target:
         left = mid + 1
         continue
     if search_list[mid] == target:
         return mid
     if search_list[mid] > target:
         right = mid - 1
 return None

search_list = [1, 3, 4, 6, 8, 9]
print binary_search(search_list, 5)
print binary_search(search_list, 1)
print binary_search(search_list, 3)
print binary_search(search_list, 4)
print binary_search(search_list, 6)
print binary_search(search_list, 8)
print binary_search(search_list, 9)

输出:

None
0
1
2
3
4
5

本文链接:http://www.yuqiaochuang.com/post/二分查找.html

-- EOF --

Comments

""