二分查找(Binary Search)是一种在有序数组或有序区间中查找特定元素的高效算法。其基本思想是每次都通过与区间的中间元素比较,将待查找的区间缩小为之前的一半,直到找到目标值或区间被缩小为零。以下是二分查找的基本步骤:
-
初始化:确定待查找的有序数组或区间,设其起始索引为
low
,终止索引为high
。 -
计算中间索引:将区间
[low, high]
的中间索引mid
设为(low + high) // 2
。 -
比较中间元素与目标值:
-
判断是否查找完毕:如果
low
大于等于high
,说明区间已被缩小为零,目标值不存在于数组中,返回特定的“未找到”标记(如-1
或None
)。
时间复杂度:
- 最好情况(目标值位于数组中间位置):查找过程可能需要比较 log_2(n) 次(向上取整),时间复杂度为 O(logn)。
- 最坏情况(目标值位于数组的第一个或最后一个位置):查找过程同样需要比较 log_2(n) 次,时间复杂度为O(logn)。
- 平均情况:查找过程需要比较约 log_2(n) 次,时间复杂度为O(logn)。
空间复杂度:二分查找仅需要常数级别的额外空间,用于存储中间索引等临时变量,因此空间复杂度为O(1)。
二分查找要求数据结构为有序且支持随机访问(如数组),在数据规模较大时具有较高的查找效率。以下是二分查找的Python实现:
Python
1def binary_search(arr, target):
2 low = 0
3 high = len(arr) - 1
4
5 while low <= high:
6 mid = (low + high) // 2
7 mid_value = arr[mid]
8
9 if mid_value == target:
10 return mid # 目标值找到,返回其索引
11 elif mid_value < target:
12 low = mid + 1 # 目标值可能在中间元素的右侧,缩小查找区间
13 else:
14 high = mid - 1 # 目标值可能在中间元素的左侧,缩小查找区间
15
16 return -1 # 目标值未找到,返回特定标记
17
18# 示例
19data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
20target = 4
21result = binary_search(data, target)
22if result != -1:
23 print(f"Target found at index {result}")
24else:
25 print("Target not found")
通过不断比较中间元素与目标值,调整查找区间,找到目标值时返回其索引,未找到时返回-1
。