二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
pdl二分查找充分利用了序列元素的递增性质,采用分治策略搜索目标值(目标值存在于序列中),目标值的左边界和右边界(目标值不存在于序列中),其中左边界指的是最大的小于目标值的元素,右边界指的是最小的大于目标值的元素。
二分查找法最坏情况
n个数, 比较中间的数,一次去掉一半,余下n/2个
n/2个数, 再比较中间的数,一次去掉一半,余下n/4个
n/4个数, 再比较中间的数,一次去掉一半,余下n/8个
n/8个数, 再比较中间的数,一次去掉一半,余下n/16个
二分查找和分块查找顺序查找相当于遍历数组的所有元组,所以不需要排序二分查找需要排序,因为每次都是和中间值比较,如果大于选中间值后面的部分继续二分查找,如果小于中间值则选前面的部分继续执行分块查找中需要按照数值大小进行排序分块,虽然每个块中的大小可以不排序,但是块的取值区间是排序的。
二分查找算法是一种快速的查找算法。当我们再一个数组中查找是否存在某个数时,通常是直接遍历这个数组直到找到这个数,时间复杂度为O(n)试想如果数据量很大,这里可以用一种简单快速的的查找算法--二分查找算法,也叫做折半查找算法。
二分查找算法,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法。它的思想是每次拿数组中间的值和目标值进行比较,不断缩小查找范围。
以下是用Python编写的简单的二分查找算法示例:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
在使用二分查找算法时,需要保证操作的数组是有序的。只有在有序的数组中才能利用二分查找的优势。
注意:二分查找算法主要应用于静态查找表,不适用于频繁变动的数组。
二分查找算法的时间复杂度为O(log n),其中n是数组的长度。这使得它成为一种高效的查找算法。
通过这篇文章,你不仅了解了二分查找算法的原理和Python实现的代码示例,还掌握了它的适用范围和时间复杂度。希望这对你理解和应用二分查找算法有所帮助。
感谢你阅读本文,希望对你有所帮助!
顺序查找的基本思想:
就是遍历整个列表,逐个进行记录的关键字与给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查的记录。如果直到最后一个记录,其关键字和给定值比较都不等时,则表中没有所查的记录,查找失败。
二分查找的基本思想是:
在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到找到为止。
因为二分查找可以很有效的缩短查找时间,提高查找效率,非常实用的方法
不是同一个概念。折半是对半成百分之五十。二分是百分之二十。
二分法就是一种在有序数组中查找某一特定元素的搜索算法。