【每日一算法】二分查找

书籍通常按顺序排列（字母顺序或字母数字顺序），这就是二分查找适用的场景。你可以快速排除一半的书籍，每次比较后再缩小范围，迅速定位目标书籍。这比逐页查找要高效得多。

二分查找是一种算法，其输入是一个有序的元素列表（必须有序二分查找（Binary Search），也称折半查找，是一种在有序数组中查找特定元素的高效算法。它可以快速找到目标值的索引（如果存在），否则返回null。

• 数组必须是有序（通常是升序或降序）。
• 数据类型必须允许比较（如数字、字符串等）。

1. 初始化两个指针：low（初始为数组首元素索引）和 high（初始为数组末尾元素索引）。

2. 在 low <= high 的情况下循环执行以下步骤：

   • 计算中间索引 mid：mid = (low + high) // 2。

   • 将目标值与数组中位于 mid 的元素进行比较：

     • 如果目标值等于数组的中间元素，返回 mid（找到目标）。

     • 如果目标值小于中间元素，说明目标位于左半部分，更新 high = mid - 1。

     • 如果目标值大于中间元素，说明目标位于右半部分，更新 low = mid + 1。

3. 如果循环结束仍未找到目标值，返回 -1（表示未找到）。

def binary_search(arr, target):low = 0high = len(arr) - 1while low <= high:mid = (low + high) // 2  # 计算中间索引if arr[mid] == target:return mid  # 找到目标elif arr[mid] < target:low = mid + 1  # 目标可能位于右半部分else:high = mid - 1  # 目标可能位于左半部分return -1  # 未找到目标# 测试
my_list = [1, 3, 5, 7, 9]
target = 3
result = binary_search(my_list, target)
if result != -1:print(f"元素 {target} 在数组中的索引是 {result}")
else:print(f"未找到元素 {target}")

时间复杂度为 O(log n) ，这是由于每次都将查找范围减少一半，因此非常适合大规模数据的快速查找。

以下是一些实际应用场景：

在企业员工管理系统中，可以根据员工编号（有序）快速查找员工信息。

# 假设员工信息存储为按员工号升序排列的列表
employees = [{"id": 100, "name": "Alice", "position": "Manager"},{"id": 200, "name": "Bob", "position": "Engineer"},{"id": 300, "name": "Charlie", "position": "HR"}
]# 查找员工号为 200 的员工信息
def find_employee_by_id(id_list, target_id):return binary_search(id_list, target_id)# 员工号列表（有序）
id_list = [100, 200, 300]
target_id = 200
index = find_employee_by_id(id_list, target_id)
if index != -1:employee = employees[index]print(f"找到员工：{employee['name']}，职位：{employee['position']}")
else:print("未找到该员工")

在库存管理系统中，产品按编号或名称字母顺序存储，二分查找可用于快速定位特定产品。

• 数据必须有序：否则二分法无法正确工作。如果输入是无序的，需要先排序。
• 边界条件处理：
  • 如果数组为空，函数应该返回 None 或 -1。
  • 如果数组长度为 1 或 2，要确保逻辑正确。

二分法通过分治思想，将问题规模不断缩小，从而快速定位目标元素。时间复杂度为 O(log n)，非常高效，是处理有序数据时的强大工具。