python_算法_二分查找

不建议大家看这篇文章, 因为我自己看着都头晕 二分查找: 二分查找的前提条件是:

只能在有序的列表内进行查找

精简版:
def bin_search(data, find_num): first = 0 last = len(data)-1 while first <= last: mid = (first+last)//2 if data[mid] == find_num: return mid if data[mid] < find_num: first = mid + 1 if data[mid] > find_num: last = mid - 1else: not_find_num = "没找到" return not_find_num

啰嗦版:
def bin_search(data, find_num): # 起始下标 first = 0 # 终止下标 last = len(data)-1 # 如果这个序列不为空就要一直查找 while first <= last: # 设置中间下标, mid = (first+last)//2 # 如果中间的数, 等于要查找的数, 返回这个数的下标 if data[mid] == find_num: return mid# 如果中间的数, 小于要查找的数, 将中间数的下标加一, 作为下一步要查找的起始下标 if data[mid] < find_num: first = mid + 1 # 如果中间的数, 大于要查找的数, 将中间数的下标减一, 作为下一步要查找的末尾下标 if data[mid] > find_num: last = mid - 1else: not_find_num = "没找到" return not_find_num '''关于下标加一减一的问题: 因为中间数已经跟要查找的数进行比对了, 1. 如果相等跳出循环,返回要查找的值 2. 如果大于, 就减一 3. 如果小于, 就减一'''

二分查找的基本思想:精简版
1. 在一个有序的列表内,查找你想要的数字. 2. 先设定起始下标,与结束下标,然后取出中间下标的值 3. 让中间坐标的值,与要查找的值进行比对 1.如果中间值等于要查找的值,直接返回中间值 2.如果中间值,小于要查找的值,那么将中间值的下标加一,作为下一次查找的起始下标 3.如果中间值,大于要查找的值,那么将中间值的下标减一作为下一次查找的终止下标 注释:关于中间值下标加一减一的操作 因为中间值已经跟要查找的值进行比对了 1.如果相等跳出循环,返回要查找的值 2.如果大于,下一次寻找的值,当然不包含当前值,所以进行坐标减一操作 3.如果小于,原理同上 4. 按照此原理直到找到为止

二分查找的基本思想:啰嗦版
1. first_num = 0#起始下标 2. last_num = len(data)-1#终止下标 3. mid_num = (first_num+last_num)//2#中间坐标 4. find_num#要查找的坐标 5. data #列表1. 在一个有序的列表内(data),查找你想要的数字(find_num). 2. 先设定起始下标(first_num),与结束下标(last_num),然后取出中间下标的值(mid_num) 3. 让中间坐标的值data[mid_num],与要查找的值进行比对(find_num)1.如果中间值等于要查找的值,直接返回中间值 if data[mid] == find_num: return data[mid] 2.如果中间值,小于要查找的值,那么将中间值的下标加一,作为下一次查找的起始下标 if data[mid] < find_num: first_num = mid_num + 13.如果中间值,大于要查找的值,那么将中间值的下标减一作为下一次查找的终止下标 if data[mid] > find_num: last_num = mid_num -1 注释:关于中间值下标加一减一的操作 因为中间值已经跟要查找的值进行比对了 1.如果相等跳出循环,返回要查找的值 2.如果大于,下一次寻找的值,当然不包含当前值,所以进行坐标减一操作 3.如果小于,原理同上 4. 按照此原理直到找到为止

二分查找演示:
import time# 先定义一个计算Demo运行时间的装饰器 def GetRunTime(func): def call_func(*args, **kwargs): begin_time = time.time() ret = func(*args, **kwargs) end_time = time.time() Run_time = end_time - begin_time print(str(func.__name__)+"函数运行时间为"+str(Run_time)) return ret return call_func# 二分查找 @GetRunTime def bin_search(data, find_num): first = 0 last = len(data)-1 while first <= last: mid = (first+last)//2 print("演示下查找的过程"+str(data[mid])) if data[mid] == find_num: return mid if data[mid] < find_num: first = mid + 1 if data[mid] > find_num: last = mid - 1else: not_find_num = "没找到" return not_find_numdata = https://www.it610.com/article/list(range(1000000)) print("二分查找:" + str(bin_search(data, 200)))

演示如下: python_算法_二分查找
文章图片
二分查找.png

    推荐阅读