数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究二分查找的 Python 程序
在本文中，我们将学习解决给定问题陈述的解决方案和方法。
问题陈述 − 我们将获得一个排序好的列表，我们需要借助二分查找查找其中一个元素。
算法
将 x 与中间元素进行比较。
如果 x 与中间元素匹配，我们就返回中间索引。
否则，如果 x 大于中间元素，则 x 只可能位于中间元素之后的右半子数组中。因此，我们对右半部分进行递归。
否则（x 较小），我们对左半部分进行递归
递归算法
示例
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index "+str(result))
else:
print ("Element is not present in array")迭代算法
示例
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index "+str(result))
else:
print ("Element is not present in array")Element is present at index 4
结论
在本文中，我们学习了应用二分查找的方法。
更新时间： 2019 年 9 月 25 日
6 千多次浏览
广告