Python 二分查找
Python3 实例二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
实例 : 递归
# 返回 x 在 arr 中的索引，如果不存在返回 -1
def binarySearch (arr, l, r, x):
# 基本判断
if r >= l:
mid = int(l + (r - l)/2)
# 元素整好的中间位置
if arr[mid] == x:
return mid
# 元素小于中间位置的元素，只需要再比较左边的元素
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# 元素大于中间位置的元素，只需要再比较右边的元素
else:
return binarySearch(arr, mid+1, r, x)
else:
# 不存在
return -1
# 测试数组
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# 函数调用
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("元素在数组中的索引为 %d" % result )
else:
print ("元素不在数组中")
执行以上代码输出结果为：
元素在数组中的索引为 3
小花花
124***4671@qq.com
'''二分查找有序不重复数组 BinarySearch(unfinished).py''' # 未完成版 def BinarySearch(sortedlist): num = int(input('Number:\t')) counter = 0 # 记录循环次数 mid = 0 # 记录中间位置 if num in [sortedlist[0], sortedlist[len(sortedlist) - 1]]: # 切割时取不到首尾 print('Find it at beginning or end.') else: while True: # 切割数组 mid = len(sortedlist) // 2 if sortedlist[mid] == num: print('Find number {}.'.format(num)) break elif sortedlist[mid] > num: sortedlist = sortedlist[:(mid + 1)] else: sortedlist = sortedlist[mid:] print(sortedlist, mid) counter += 1 if counter > len(sortedlist) + 1: # 超过迭代次数即停止 print('Don\'t find it.') break sortedlist = [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] BinarySearch(sortedlist)小花花
124***4671@qq.com
叫爸爸
506***262@qq.com
该算法的要求：
def bin_search(data_list, val): low = 0 # 最小数下标 high = len(data_list) - 1 # 最大数下标 while low <= high: mid = (low + high) // 2 # 中间数下标 if data_list[mid] == val: # 如果中间数下标等于val, 返回 return mid elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标 high = mid - 1 else: # 如果val在中间数右边, 移动low下标 low = mid + 1 return # val不存在, 返回None ret = bin_search(list(range(1, 10)), 3) print(ret)叫爸爸
506***262@qq.com
ccneko
ccn***@163.com
补充个增序或者减序都能用的版本：
# 二分查找（非递归版本） # isAsc为True时，列表增序，否则减序 def binarySearch(sortedList, key, isAsc=True): left = 0 # 查找范围最左边的下标 right = len(sortedList) - 1 # 查找范围最右边的下标 while left <= right: # mid = left + right >> 1 # 中间数下标（向下取整） if isAsc and sortedList[mid] < key \ or not isAsc and sortedList[mid] > key: # key在中间数右边时，查找范围变为右边 left = mid + 1 elif isAsc and sortedList[mid] > key \ or not isAsc and sortedList[mid] < key: # key在中间数左边时，查找范围变为左边 right = mid - 1 else: return mid # key为中间数时，返回其下标 return -1ccneko
ccn***@163.com
东坡弃疾
158***48554@163.com
有序不重复数组，二分查找，非递归算法：
def binaryserch(a,x): mid = tempmid =len(a) // 2 #mid 用于记录数组a的中间数，tempid 用于记录原始数组中mid的值 while len(a) > 1: if a[mid] > x: a = a[:mid] mid = len(a) // 2 tempmid = tempmid - (len(a) - mid) elif a[mid] < x: a = a[mid+1:] mid = len(a) // 2 tempmid = tempmid + mid +1 else: break if len(a) == 1: tempmid = tempmid if a[mid]== x else -1 if len(a) < 1: tempmid = -1 return tempmid东坡弃疾
158***48554@163.com