Python程序实现不使用递归的二分查找

当需要实现二分查找但不使用字典时，可以定义一种方法，检查列表的第一个和最后一个索引，并获取列表的中值。

然后将其与需要检查的值进行比较。如果找到，则返回该值。否则，返回-1。

重要的是记住，二分查找仅适用于已排序的元素，无论是升序还是降序。

列表可用于存储异构值（即任何数据类型的数据，例如整数、浮点数、字符串等）。

以下是相同操作的演示 —

例子

def binary_search(my_list, elem):
   low = 0
   high = len(my_list) - 1
   mid = 0
   while low <= high:
      mid = (high + low) // 2
      if my_list[mid] < elem:
         low = mid + 1
      elif my_list[mid] > elem:
         high = mid - 1
      else:
         return mid
   return -1

my_list = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
elem_to_search = 1
print("该列表为")
print(my_list)

my_result = binary_search(my_list, elem_to_search)

if my_result != -1:
   print("元素索引为", str(my_result))
else:
   print("未找到元素！")

输出

该列表为
[1, 9, 11, 21, 34, 54, 67, 90]
元素索引为 0

解释

• 定义名为“binary_search”的方法，将列表和要搜索的元素作为参数。
• 将变量low分配给0，将变量mid分配给0。
• 变量high被分配为列表的长度-1。
• 当值“low”小于或等于“high”时，执行位运算除法以获取“mid”变量的值。
• 首先从低到中索引搜索元素，如果该值小于中索引处的值。
• 否则，如果该值大于中且小于高，则从中到高索引搜索元素。
• 现在定义一个列表。
• 通过将上面的列表作为参数调用该方法。
• 将此操作的数据存储在变量中。
• 该变量是在控制台上显示的输出。