题目描述
给定一个升序排列的整数数组 A 和一个整数 Q,表示接下来有 Q 次查询。对于每次查询,您需要判断给定的整数 x 是否存在于数组 A 中。请使用二分查找算法实现这一功能。
输入格式
输出格式
对于每个查询,输出一行:
示例
输入:
5 3
1 3 5 7 9
3
2
9
输出:
YES
NO
YES
二分算法是一种高效的查找算法,适用于已经排好序的数组或集合。其基本思想是通过每次将待查找的区间分成两半来逐步缩小查找范围,从而快速定位目标元素。与线性查找不同,二分查找能够大大减少查找次数,时间复杂度为O(log n),其中n为数组的长度。
一. 前提条件:二分法的数据必须满足单调性:
这是因为二分法的核心思想是通过比较目标值和中间值来决定下一步搜索的区间。如果数据不是单调的,那么我们无法保证每次通过中间值进行判断后,能够缩小问题的范围,从而导致无法正确找到目标值。
具体来说,二分算法依赖于以下几个关键步骤:
如果数据是单调递增的,意味着任何一个位置的值都比它前面的值大。这样我们就可以通过比较目标值与中间值来决定是往左还是往右缩小区间。相反,如果数据不是单调递增或递减的,那么目标值可能出现在区间的任何位置,二分算法就无法有效地通过比较来缩小查找范围,导致无法正确查找。
二. 查找过程:
low
和 high
。mid = (low + high) / 2
high = mid - 1
。low = mid + 1
。low > high
),即目标值不存在。三. 时间复杂度:二分查找的时间复杂度是O(log n),每次查找都将查找范围缩小一半。因此,二分查找的效率远高于线性查找(O(n))。
四. 适用场景:
确定二分查找的范围
二分查找的查找范围就是整个数组的区间,即数组的下标从 0 到 A.size() - 1
。我们将 low
设置为 0,high
设置为数组的最后一个下标。
left = 0
right = len(A) - 1
计算中间元素
每次进行二分查找时,我们需要计算当前查找区间的中间元素 mid
,并将其与目标值进行比较。为了防止溢出,我们用 mid = (left + right) // 2
来计算。
mid = (left + right) // 2 # 计算中间元素
判断中间元素与目标值的关系
A[mid] == x
,说明我们找到了目标值,返回 True
。A[mid] < x
,说明目标值可能在右半部分,更新左边界 left = mid + 1
。A[mid] > x
,说明目标值可能在左半部分,更新右边界 right = mid - 1
。if A[mid] == x:
return True # 找到目标值
elif A[mid] < x:
left = mid + 1 # 目标值在右半部分
else:
right = mid - 1 # 目标值在左半部分
终止条件
当查找区间为空(即 left > right
),说明目标值不存在,返回 False
。
return False # 没有找到目标值
def binary_search(A, x):
# 初始化查找范围的左右边界
left = 0
right = len(A) - 1
# 当查找范围有效时进行循环
while left <= right:
mid = (left + right) // 2 # 计算中间元素
# 判断中间元素与目标值的关系
if A[mid] == x:
return True # 找到目标值,返回True
elif A[mid] < x:
left = mid + 1 # 目标值在右半部分,更新左边界
else:
right = mid - 1 # 目标值在左半部分,更新右边界
return False # 没有找到目标值,返回False
def main():
# 读取数组长度n和查询次数Q
n, Q = map(int, input().split())
# 读取升序数组A
A = list(map(int, input().split()))
# 对每个查询进行二分查找
for _ in range(Q):
x = int(input()) # 每次查询的目标值
# 调用二分查找函数,输出查询结果
if binary_search(A, x):
print("YES")
else:
print("NO")
if __name__ == "__main__":
main()