二分查找
二分查找也称 折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
二分查找
前提条件
数组有序
时间复杂度
二分搜索方法充分利用了元素间的次序关系,采用分治策略,可在最坏情况下用 \(O(logn)\) 时间完成搜索任务
基本思想
将 n 个元素分成个数大致相同的两半,取 a[n/2]
与 x 进行比较。
如果x=a[n/2]
,则找到 x,算法终止。
如果 x<a[n/2]
, 则只要在数组 a 的左半部继续搜索 x。
如果 x>a[n/2]
,则只要在数组 a 的右半部继续搜索 x。
Java 实现
- 非递归
1 | public static int binarySearch(int[] arr, int target) { |
- 递归
1 | public static int binarySearch2(int[] arr, int target, int left, int right) { |
C 实现
1 | int binary_search(int* a, int left, int right, int target) { |
References
-
2019-05-24
-
2019-06-03
这篇文章主要总结了面试中需要掌握的几个方面,包括数据结构、算法和数据操作、高质量的代码、解决面试题的思路、优化时间和空间效率以及面试中的各项能力。在数据结构方面,需要掌握常见的数据结构,如数组、链表、栈、队列、树、图等,并能够熟练地进行操作。在算法和数据操作方面,需要掌握常见的算法,如排序、查找、递归、动态规划等,并能够熟练地运用到实际问题中。在高质量的代码方面,需要注意代码的可读性、可维护性和可扩展性,并且要遵循一定的编码规范。在解决面试题的思路方面,需要掌握常见的解题思路,如暴力枚举、贪心算法、分治算法等,并能够灵活运用到实际问题中。在优化时间和空间效率方面,需要注意算法的时间复杂度和空间复杂度,并能够对算法进行优化。在面试中的各项能力方面,需要注意沟通能力、团队合作能力、问题解决能力等。
-
2019-06-08
Deepin Screenshot,一个简洁易用的截图工具。
-
2019-05-24
在计算机科学中,选择排序(Selection sort)是一种排序算法,切确的说是就地比较排序。它具有 \(O(n^2)\) 时间复杂度,使其在大型列表上效率低下,并且通常比类似的插入排序更差。选择排序因其简单性而着称,并且在某些情况下具有优于更复杂算法的性能优势,特别是在辅助存储器有限的情况下。
-
2020-05-02
通常,实现二叉树的前序(preorder)、中序(inorder)、后序(postorder)遍历的迭代版本都需要 O(n) 的空间复杂度,那么有没有可能使用 O(1) 空间进行迭代遍历呢?答案是肯定的。
本文将介绍 Morris Traversal 遍历二叉树的方法,该算法能够做到 O(1) 空间复杂度的迭代遍历,并在遍历完成后二叉树依然保持原始状态(遍历过程中可能被修改)。