二分查找的 Python 程序

pythonserver side programmingprogramming更新于 2025/12/14 15:08:17

在本文中，我们将了解解决给定问题陈述的解决方案和方法。

问题陈述 − 我们将获得一个排序列表，我们需要借助二分查找找到一个元素。

算法

将 x 与中间元素进行比较。
如果 x 与中间元素匹配，我们返回中间索引。
否则，如果 x 大于中间元素，则 x 只能位于中间元素后的右半子数组中。因此我们对右半部分进行递归。
否则(x 较小)对左半部分进行递归

递归算法

示例

def binarySearchAppr (arr, start, end, x):
# 检查条件
if end >= start:
   mid = start + (end- start)//2
   # 如果元素存在于中间
   if arr[mid] == x:
      return mid
   # 如果元素小于 mid
   elif arr[mid] > x:
     返回 binarySearchAppr(arr, start, mid-1, x)
   # 否则元素大于 mid
   else:
      return binarySearchAppr(arr, mid+1, end, x)
   else:
   # 数组中未找到元素
      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 ("元素存在于索引处"+str(result))
else:
print ("元素不存在于数组中")

迭代算法

示例

def binarySearchAppr (arr, start, end, x):
# 检查条件
   if end >= start:
      mid = start + (end- start)//2
      # 如果元素存在于中间
      if arr[mid] == x:
      return mid
      # 如果元素小于 mid
      elif arr[mid] > x:
      return binarySearchAppr(arr, start, mid-1, x)
      # 否则元素大于 mid
      else:
      return binarySearchAppr(arr, mid+1, end, x)
   else:
      # 数组中未找到元素
      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 ("元素存在于索引处"+str(result))
else:
   print ("元素不存在于数组中")