宁波模板建站定制,wordpress hacker主题,基于wordpress,百度推广后台登陆折半查找#xff08;Binary Search#xff09;#xff0c;也称为二分查找#xff0c;是一种在有序数组中查找特定元素的搜索算法。其工作原理是#xff0c;通过不断将待查找的区间分成两半#xff0c;并判断待查找的元素可能存在于哪一半#xff0c;然后继续在存在可能性…折半查找Binary Search也称为二分查找是一种在有序数组中查找特定元素的搜索算法。其工作原理是通过不断将待查找的区间分成两半并判断待查找的元素可能存在于哪一半然后继续在存在可能性的那一半区间中查找直到找到该元素或者区间被缩小为0为止。
折半查找的基本步骤
1、初始化
确定查找范围的上下界即查找区间的起始位置low和结束位置high通常初始时low 0high 数组长度 - 1。
2、循环查找
当low high时执行以下步骤
计算中间位置mid (low high) // 2注意使用整除以避免浮点数。 判断中间位置的元素是否是要查找的元素即arr[mid] target 如果是则查找成功返回中间位置mid或该位置的索引mid取决于具体实现。 如果不是则判断target与arr[mid]的大小关系并据此调整查找范围 如果target arr[mid]则说明target在左半部分更新high mid - 1。 如果target arr[mid]则说明target在右半部分更新low mid 1。
3、查找失败
如果循环结束时仍未找到target则说明数组中不存在该元素返回查找失败的信息通常是-1或特定值。
折半查找的Python示例
def binary_search(arr, target):折半查找二分查找:param arr: 有序数组:param target: 要查找的目标值:return: 目标值在数组中的索引如果未找到则返回-1low, high 0, len(arr) - 1while low high:mid (low high) // 2if arr[mid] target:return mid # 找到目标值返回索引elif arr[mid] target:low mid 1 # 调整查找范围到右半部分else:high mid - 1 # 调整查找范围到左半部分return -1 # 未找到目标值返回-1# 示例
arr [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target 7result binary_search(arr, target)
print(f元素{target}在数组中的索引为{result}) # 输出元素7在数组中的索引为3折半查找的优缺点
优点 查找速度快时间复杂度为O(log n)其中n是数组的长度。 对于大数据集查找效率远高于顺序查找。
缺点 要求待查找的数组必须是有序的。 数组必须有随机访问的能力即可以使用索引直接访问元素这限制了它在链表等数据结构上的应用。 当数据集非常大时需要较大的内存空间来存储整个数组。
