二分查找

二分查找

二分查找可以实现 O(logn) 的时间复杂度,直观一点说,2 的 32 次方,大概 42 亿,最多需要比较 32 次就可以查找到数据。二分查找的原理就是,每次都将数据一分为二,通过被查找元素和中间的元素对比,判定下次查找是在中点的左边还是右边,即将待查找的区间缩小为之前的一半,直到找到要查找的元素。

使用二分查找的约束条件

  • 依赖数组
    • 二分查找需要按照下标随机访问首、尾、中间的元素所以需要数组,如果基于链表实现,时间复杂度会从 O(logn) 退化成 O(n) 的
    • 因为是基于数组的,所以内存空间是连续的,大数据量的情况下可能会没有那么大连续内存
  • 数据是有序的
    • 数据必须是有序的,如果数据没有序,首先需要先排序
    • 适用于查多改少的场景,因为要维护数据的有序性,插入、删除操作的复杂度会很高

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1, mid;
while (left <= right) {
mid = (right - left) / 2 + left;
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}

变体问题

  • 有序数据集合中存在重复的数据,找到 第一个 / 最后一个 等于给定值的数据
  • 搜索旋转排序数组

总结

本周的学习内容还包含 DFS、BFS 这个两个已经老生常谈的算法了。我们之前在练习二叉树的前、中、后序遍历的时候就是深度遍历,全排列、组合、子集、生成括号等回溯算法解决问题的时候也是深度优先遍历。练习二叉树层序遍历、全排列、岛屿数量可以用广度优先解决,有时候用广度优先能解决的问题用深度优先也可以解决,因为在深度优先遍历的时候,我们是知道遍历的深度 level 的。通常情况下,用迭代法解决深度优先遍历会用到 ,因为栈可以方便我们回溯到上个节点继续遍历。迭代法解决广度优先遍历会用到 队列,我们将每一层的节点入队,并遍历 poll 出当前层的所有节点,依次处理,如果处理的当前层的节点还有下层节点,再次入队,往复处理直到队列为空。

关于贪心算法,打算在下下周学完动态规划一起总结,这个是继 分治回溯 后的最后两个算法思想。全部学完后,可以比较一下它们的异同,解决问题的适用范围。

二分查找可以实现 O(logn) 的时间复杂度,但是这个是有前提的。首要需要使用数组保持数据,即可随机访问、内存连续的;其次数据要是有序的,所以插入、删除数据时,为了保持有序需要付出额外的代价,或者说需要对数据进行排序,也就是说二分查找比较适查多写少的场景。最后要理解记忆二分查找的代码模板,能够用二分查找解决一些变体情况。

坚持原创技术分享,您的支持将鼓励我继续创作!