不建议大家看这篇文章, 因为我自己看着都头晕
二分查找:
二分查找的前提条件是:
只能在有序的列表内进行查找
精简版:
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 - 1
else:
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 - 1
else:
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 + 1
3.如果中间值,大于要查找的值,那么将中间值的下标减一作为下一次查找的终止下标
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 - 1
else:
not_find_num = "没找到"
return not_find_num
data = list(range(1000000))
print("二分查找:" + str(bin_search(data, 200)))
演示如下:
二分查找.png
