看见朋友圈满屏的 99999 ,才反应过来一年一度 520 到了。作为单身狗,今天本来“雨我无瓜”,但我有个朋友(无中生“友”)说想快点找到对象?那二分查找算法了解一下。
二分查找算法(binary search algorithm),也称折半搜索算法(half-interval search algorithm),是一种在有序数组中查找某一特定元素的搜索算法(引自维基百科)。搜索过程是从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
以上面的动图为例,要在 1~35 的 16 个元素中找到 37 ,使用二分法则只需要 3 步,而遍历查找需要 11 步。
二分查找的查找过程如下:
(0+16)/2 = 8
个元素与 37 的大小;知道了算法运行的原理,接下来我们用 Stata 比较几种方式的查找效率。**我们要解决的问题是:假设有 1~999999 个有序数字,从中查找 5201314 **。用代码表示:
clear
set rmsg on //show how long the command took
set obs 9999999
gen n = _n
scalar target = 5201314
* 遍历查找
forvalues guess = 1/`=_N'{
if `guess' == target{
dis "找到" target "啦!"
continue, break
}
}
/*
Output:
找到 5201314 啦!
r; t=42.98 10:55:14
*/
local low = 1
local high = `=_N'
while `low' <= `high'{
local mid = (`low' +`high') / 2
local guess = n[`mid']
if `guess' == target{
dis "找到 " target " 啦!"
continue, break
}
if `guess' > target{
local high = `mid' - 1
}
else{
local low = `mid' + 1
}
}
/*
Output:
找到 5201314 啦!
r; t=0.00 10:55:32
*/
python:
from sfi import Data
import time
def binary_search(n, target):
low = 0
high = len(n) - 1
while low <= high:
mid = int((low + high)/2)
guess = n[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return None
n = Data.get(var='n')
target = 5201314
start = time.time()
binary_search(n,target)
end = time.time()
print("耗时:{}".format(end-start))
end
/*
Output:
耗时:0.0009615421295166016
*/
从运行的结果来看,遍历查找需要 42 秒左右,而二分查找的速度快多了,简直是秒杀。二分查找作为经典的算法,日常生活中挺实用的,比如从通讯录查找某姓氏开头朋友的电话、根据学号查找对应的姓名等,都能够派上用场。今天的推文到这里就结束了,你看完后掌握了如何快速找对象的方法了吗?
,520 还在写代码的就别想了。最后,祝单身 dog 早日脱单,有情人终成眷属,完结撒花!