本篇 ShengYu 介紹 Python 二元搜尋法 Binary Search。
Python Binary Search 二元搜尋法(迴圈版本)
這篇介紹 C/C++ Binary Search 二元搜尋法迴圈的版本，遞迴的版本下一節會介紹到，要使用二元搜尋法前有個前提，就是必須要確認資料是已排序過的，如果資料未排序可以用 sort 來先排序，接著使用迴圈每次將 key 值與中間值作比較，如果 key 值大於中間值的話，下次就往右側搜尋，右側為值較大的一邊，否則就往左側搜尋，左側為值較小的一邊，這的動作一直持續到比對到符合的 key 值或者迴圈結束未找到 key 值，範例如下，1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#!/usr/bin/env python3
# -*- coding: utf-8 -*-
def binary_search(data, key):
low = 0
high = len(data)-1
while low <= high:
mid = int((low + high) / 2)
if key == data[mid]:
return mid
elif key > data[mid]:
low = mid + 1
else:
high = mid - 1
return -1
data = [1, 9, 2, 7, 4, 10, 3, 8, 5, 6]
key = 7
data.sort()
print(data)
ret = binary_search(data, key)
if ret == -1:
print('找不到')
else:
print('找到索引值' + str(ret))
輸出結果如下，1
2[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
找到索引值6
Python Binary Search 二元搜尋法(遞迴版本)
剛剛介紹的二元搜尋法是迴圈的版本，這邊要介紹二元搜尋法遞迴版本，遞迴的版本要稍微修改一下，思考方式也要稍微轉換一下，1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
# -*- coding: utf-8 -*-
def binary_search(data, low, high, key):
if low > high:
return -1
mid = int((low + high) / 2)
if key == data[mid]:
return mid
elif key > data[mid]:
low = mid + 1
return binary_search(data, low, high, key)
else:
high = mid - 1
return binary_search(data, low, high, key)
data = [1, 9, 2, 7, 4, 10, 3, 8, 5, 6]
key = 7
data.sort()
print(data)
ret = binary_search(data, 0, len(data)-1, key)
if ret == -1:
print('找不到')
else:
print('找到索引值' + str(ret))
輸出結果如下，1
2[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
找到索引值6