二分查找

二分查找

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

使用二分查找的约束条件

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

代码模板

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