算法简介
二分查找也称折半查找（Binary Search），多数的人喜欢叫他二分查找。它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列，注意必须要是有序排列。
具体计算
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
具体代码如下：（phthon）
- 方式1
def serach(ls, left, right, target):
mid = (left + right) // 2
if left > right:
return "-1"
if target == ls[mid]:
return mid
elif target > ls[mid]:
left = mid + 1
elif target < ls[mid]:
right = mid - 1
else:
return "-1"
return serach(ls, left, right, target)
def main():
"""主函数"""
my_list = [1, 3, 5, 7, 10,34,56,76,89] # 有序列表
num = 34 # 要猜测的数字
print(search(my_list, 0, len(my_list)-1, num))
if __name__ == '__main__':
main()
- 方式2
"""
二分算法
:param my_list: 有序列表
:param num: 要查找的元素
:return: 存在返回下标 不存在返回NONE
"""
def binarySearch(my_list,findvalue):
left = 0
right = len(my_list) - 1
#print(right)
#print(findvalue)
while left<=right:
mid=int((left+right)/2)
if my_list[mid]==findvalue:
return mid
if my_list[mid]<findvalue:
left=mid+1
if my_list[mid]>findvalue:
right=mid-1
return None
def main():
"""主函数"""
my_list = [1, 3, 5, 7, 10,34,56,76,89] # 有序列表
num = 34 # 要猜测的数字
print(binarySearch(my_list, num))
if __name__ == '__main__':
main()