七大查找算法之有序表查找

2024-07-16 12:24| 来源: 网络整理| 查看: 265

二分查找

二分查找也称为是折半查找，属于有序查找算法。元素必须是有序的，如果是无序的则要先进行排序操作。二分查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，二分查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

原理：

二分查找用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

算法详细描述：选择一个可以将列表arr大致一份为二的索引i；检查是否有arr[i] == target；如果不是，检查arr[i]大于还是小于target；根据上一步的结果，确定在arr的左半部分还是右半部分搜索target。代码实现： ## 递归版本 def binarySearch(arr, target): """ 假设arr是列表,其中元素按升序排列. 如果target是arr中的元素,则返回True,否则返回False """ def bSearch(arr, target, low, high): if high == low: return arr[low] == target mid = (low + high) // 2 if arr[mid] == target: return True elif arr[mid] > target: if low == mid: return False else: return bSearch(arr, target, low, mid - 1) else: return bSearch(arr, target, mid + 1, high) if len(arr) == 0: return False else: return bSearch(arr, target, 0, len(arr) - 1) ## 非递归版本 def binarySearch(arr, target): low = 0 high = len(arr) - 1 while low < high: mid = (low + high) // 2 if target < arr[mid]: high = mid - 1 elif target > arr[mid]: low = mid + 1 else: return True return False 时间复杂度：

假设，总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。由于n/2^k取整后>=1，即令n/2^k=1，可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)

【本文地址】

七大查找算法之有序表查找

七大查找算法之有序表查找

今日新闻

推荐新闻