python_算法_二分查找 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)))

演示如下: