还记得我第一次看算法的时候,是一本叫做大话数据结构的书,还是我的学长推荐给我,再后来是学校里教的严蔚敏版的数据结构,再到后来看K神的Hello算法,严蔚敏版的比较专业和全面,大话数据结构以及Hello算法两本书语言幽默,尤其是K神的每章总结非常之精辟,再后来跟着黑马还有代码随想录的视频过了一遍,看看它们又是如何写算法题的,至于我的力扣,我只写了包括简单题在内的200多道,我刷的有点少了,主要在坚持,只坚持了很短一段时间,大概三四天一道

算法初识

算法: 程序员的致胜法宝

作为开发人员,我们都知道算法就像是我们的瑞士军刀 - 多功能,精准,而且在关键时刻总能救你一命。

定义

在数学和计算机科学领域,算法是一系列有限的严谨指令,通常用于解决一类特定问题或执行计算。

理解

算法就是我们在深夜Debug时的救命稻草,是在代码评审中让同事眼前一亮的秘密武器,更是在性能优化时的制胜法宝。

简单来说,算法就是:

输入：一堆看似毫无关联的数据
过程：一系列巧妙到令人发指的操作
输出：解决问题的完美方案

而且整个过程必须在产品经历规定的deadline之前完成, 否则等待你的可能就是无尽的加班了

所以,下次当你看到一个程序员对着屏幕露出诡异的笑容时,别慌,ta可能只是想到了一个绝妙的算法,正在享受即将征服复杂问题的快感。毕竟,在程序员的世界里,优雅的算法就是最性感的存在!

数据结构: 程序员的积木游戏

作为开发者,我们都知道数据结构就像是我们的乐高积木 - 基础,灵活,而且能用它们搭建出令人惊叹的软件大厦。

定义

在计算机科学领域,数据结构是一种数据组织、管理和存储格式,通常被选择用来高效访问数据。

理解

数据结构就是我们在代码世界中的收纳神器。它就像是你桌面上的文件夹系统,只不过更加高级 - 有时候它是一列整齐的队伍(数组),有时候是一棵枝繁叶茂的树(二叉树),还有时候是错综复杂的蜘蛛网(图)。

简单来说,数据结构就是:

一种组织数据的艺术
让你的代码既整洁又高效的秘诀
在代码评审中展示你内功的绝佳机会

记住,程序 = 数据结构 + 算法。这就像是武侠小说里的内功心法和招式 - 数据结构是你的内功,算法是你的招式。两者结合,才能在代码江湖中纵横捭阖。

所以,下次当你看到一个程序员对着一堆看似杂乱无章的数据露出”我要开始装逼了”的表情时,别惊讶,ta可能只是在脑海中构建一个绝妙的数据结构,准备大展身手。毕竟,在程序员的世界里,巧妙的数据结构就是最强大的武器!

接下来,让我们通过一个经典的二分查找算法来见识一下数据结构和算法是如何携手创造奇迹的。准备好了吗?让我们开始这场代码的华尔兹吧!

二分查找: 程序员的”猜数字”游戏

各位,准备好了吗?我们即将揭秘一个堪称编程界”半夜不睡觉也要学会”的算法 —— 二分查找!

基础版：最简单的”猜数字”游戏

需求：在一个有序的数组 $A$ 中找到目标值 $t a r g e t$ 。

找到了?返回索引
没找到?返回 $- 1$

算法描述:

步骤	描述
前提	给你一个排好队的数组 $A$ ,里面有 $n$ 个元素,满足 $A_{0} \leq A_{1} \leq A_{2} \leq \dots \leq A_{n - 1}$ ,还有一个目标值 $t a r g e t$
1	设置 $i = 0$ , $j = n - 1$ (就像设置游戏的起点和终点)
2	如果 $i > j$ ,游戏结束,目标值是个”幽灵”,根本不存在
3	计算中间位置 $m = ⌊ \frac{i + j}{2} ⌋$ ( $⌊ ⌋$ 表示向下取整,就是抹掉小数部分)
4	如果 $t a r g e t < A_{m}$ ,那么把 $j$ 缩小到 $m - 1$ ,跳到第2步
5	如果 $A_{m} < t a r g e t$ ,那么把 $i$ 增大到 $m + 1$ ,跳到第2步
6	如果 $A_{m} = t a r g e t$ ,找到了!游戏结束!

在接下来的课程中,我们会用更简单直白的方式来描述算法。毕竟,我们是程序员,不是数学家,对吧? 准备好了吗?让我们开始这场惊心动魄的”猜数字”游戏吧!记住,在编程的世界里,二分查找就是你的超能力,让你在成千上万的数据中,以闪电般的速度找到目标。这项技能,足以让你在同事面前装个小小的B了!

Java实现

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {            // 目标在左边
            j = m - 1;
        } else if (a[m] < target) {     // 目标在右边
            i = m + 1;
        } else {
            return m;                   // 找到了!
        }
    }
    return -1;                          // 目标是个幽灵,根本不存在
}

解读这段代码,就像解读一个古老的魔咒:

i 和 j 就像是两个侦探,一个守左一个守右,共同缩小搜索范围。它们的活动区间是 [0, a.length-1]
while (i ⇐ j) 是魔法的持续条件。只要两个侦探还没有撞到一起,搜索就继续。
- 思考题：如果去掉 = 会怎样?
- 答案：可能会漏掉最后一个藏宝点!
m = (i + j) >>> 1 是寻找中间点的咒语。>>> 是向右位移,比普通的除以2更快
接下来就是三个分支
- 如果目标在左边,右侦探就往左移动。
- 如果目标在右边,左侦探就往右移动。
- 如果找到了,就高呼”我找到了”!
如果最后还是没找到,就返回-1,意思就是当前数组不存在这个数

记住,每次循环都会将搜索范围缩小一半,这就是二分查找的威力所在。它就像是一个不断折叠的纸张,每次都把无关的部分折掉,直到找到目标或者纸张被完全折叠。

改进版

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length;
    while (i < j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {            // 目标在左边
            j = m;
        } else if (a[m] < target) {     // 目标在右边
            i = m + 1;
        } else {
            return m;                   // 找到了!
        }
    }
    return -1;                          // 目标不在这里
}

这个版本就像是二分查找的”进化形态”,更加精炼和高效:

i 和 j 现在玩的是”左闭右开”的游戏,搜索区间是 [0, a.length)。就像是在一个半开放的博物馆里寻宝,右边的门总是虚掩着。
while (i < j) 是新的魔咒。只要两个侦探还没有相遇,搜索就继续。
- 思考题：为什么这次不需要 = 了?
- 答案：因为右边的门是虚掩的(开区间),j 指向的元素不是目标。如果加上=,就像是在已经搜索过的地方反复横跳,可能会陷入无限循环!
当缩小右边界时,我们用 j = m。这就像是把右边的门往左推,但不会完全关上

为什么用右移而不是除以2?

右移操作与整数溢出

在Java中,(i + j) >>> 1 这个操作可能会导致整数溢出的问题。这是因为如果 i 和 j 都很大,它们的和可能会超出 int 类型的范围。

例如,假设 i 和 j 都接近 Integer.MAX_VALUE:

int i = Integer.MAX_VALUE; // 2147483647
int j = Integer.MAX_VALUE; // 2147483647
int m = (i + j) >>> 1;     // 这里会出现问题

在这种情况下,i + j 会导致整数溢出,结果可能是一个负数,然后右移操作会产生一个错误的结果。

为了避免这个问题,我们可以使用一个更安全的方法来计算中间值:

int m = i + ((j - i) >>> 1);

这个方法首先计算 j 和 i 的差,然后右移一位(相当于除以2),最后加上 i。这样可以有效避免整数溢出的问题。

位操作的特性

右移操作 >>> 是在位级别进行的,它会将所有位向右移动,包括符号位。这就是为什么它可能会导致意外结果。

整数溢出

在Java中,整数溢出不会抛出异常,而是会”环绕”到另一端。这就是为什么 Integer.MAX_VALUE + 1 会得到 Integer.MIN_VALUE

为什么 i + ((j - i) >>> 1) 更安全

这个方法首先计算差值,然后除以2,最后加上 i。即使 j - i 的结果很大,右移后的值也不会超过 (j - i) 的一半,所以最终结果一定在 i 和 j 之间。

衡量算法好坏

在算法的世界里,我们不仅要写出正确的代码,还要写出高效的代码。就像赛车一样,不仅要到达终点,还要以最快的速度到达。让我们来看看两种查找算法的”赛车”较量。

线性查找

public static int search(int[] a, int k) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == k) {
            return i;
        }
    }
    return -1;
}

这个算法就像是一辆老式家用车,稳定可靠,但速度…嗯,让人略感遗憾。

在最坏情况下(目标值不在数组中),它的时间复杂度是 O(n)。简单来说,数组越长,查找时间就越长,呈线性增长。

二分查找：F1赛车

public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

这个算法就像是一辆F1赛车,速度快得惊人。它的时间复杂度是 O(log n)。

每次比较都会将搜索范围缩小一半,这就是它高效的秘诀。就像赛车手在弯道上的完美操控,每次都精准地削减了一半的路程。

性能对比：家用车 vs F1赛车

当数据规模较小时,这两种算法的表现差异并不明显。就像在拥挤的城市道路上,家用车和F1赛车的速度差异不大。

但是,当数据规模变大时,二分查找的优势就凸显出来了。就像在宽阔的赛道上,F1赛车远远甩开了家用车。例如,当 n = 1000 时:

线性查找可能需要进行1000次比较
二分查找最多只需要约10次比较 (log₂1000 ≈ 10)
这就是为什么在处理大规模有序数据时,二分查找如此受欢迎。它就像是算法世界的”尤塞恩·博尔特”,总能以惊人的速度找到终点。

记住,选择正确的算法就像选择正确的交通工具。在算法的高速公路上,让我们都成为那个开着F1赛车的程序员吧!

时间复杂度

在程序员的世界里,时间复杂度就像是算法的”速度表”。它告诉我们,当数据规模不断增大时,我们的算法会”跑”得有多快。

大O表示法

大O表示法就像是算法界的”简笔画”。它不关心细节,只抓住主要特征。就像我们形容一个人高不高,不会精确到毫米,而是说”挺高的”或”很高”。

例如:

线性查找: $O (n)$ - 就像是”跑步”,数据量翻倍,时间也翻倍
二分查找: $O (l o g n)$ - 就像是”坐直升机”,数据量翻倍,多花一点点时间就够了

如何简化到大O

去掉常数：就像买房子,我们关心是一居室还是两居室,不会在意是不是还多了个0.5平米的储藏间
保留最高次项：就像比较谁更高,我们只在意谁的身高更高,不会考虑体重
对数统一： $l o g_{2} n$ , $l o g_{1} 0 n$ , $l nn$ 都可以写作 $l o g n$ 。就像我们说”很高”,不会纠结是1米8还是1米9。

常见的时间复杂度

想象一下,这些时间复杂度是不同的交通工具:

$O (1)$ : 瞬间传送,无论距离多远,时间都一样。
$O (l o g n)$ : 直升飞机,距离越远效率越高。
$O (n)$ : 跑步,距离翻倍,时间翻倍。
$O (n l o g n)$ : 高铁,快,但还是会受到距离影响。
$O (n^{2})$ : 蜗牛,距离越远,越慢得让人发指。
$O (2^{n})$ : 用脚趾走路,别试,真的。

渐进界限

渐进上界 $O$ : 算法的”最坏情况”。就像说”这个快递最多3天送到”。
渐进下界 $Ω$ : 算法的”最好情况”。就像说”这个快递至少需要1天”。
渐进紧界 $Θ$ : 算法的”准确估计”。就像说”这个快递需要1-3天”。

空间复杂度

如果说时间复杂度是算法的”速度表”,那么空间复杂度就是算法的”存储账单”。它告诉我们,随着数据规模的增长,我们的算法会”吃掉”多少额外的内存空间。

二分查找的空间复杂度

public static int binarySearchBasic(int[] a, int target) {
    int i = 0, j = a.length - 1;    // 设置指针和初值
    while (i <= j) {                // i~j 范围内有东西
        int m = (i + j) >>> 1;
        if(target < a[m]) {         // 目标在左边
            j = m - 1;
        } else if (a[m] < target) { // 目标在右边
            i = m + 1;
        } else {                    // 找到了
            return m;
        }
    }
    return -1;
}

这个算法的空间复杂度是 $O (1)$ 。为什么?因为无论输入的数组有多大,它只使用了固定数量的额外变量(i, j, m)。这就像是无论你要找的书在多大的图书馆里,你只需要一个书签就够了。

二分查找的性能分析

时间复杂度

最坏情况: $O (lo g n)$
- 这就像是在一本1024页的书中找一个词,最多只需要翻10次。
- 即使是在一个十亿元素的数组中查找,最多也只需要约30次比较。
最好情况: $O (1)$
- 如果运气爆棚,第一次就找到了目标(比如目标正好在数组中间),那就只需要一次比较。
- 这就像你在找一本书,一进图书馆就发现它正躺在入口的展示台上。

空间复杂度: $O (1)$

无论数组多大,二分查找只需要几个额外的变量。
这就像是无论你要整理多大的衣柜,你只需要一个衣架就够了。

再看二分查找

平衡版：追求完美平衡

public static int binarySearchBalance(int[] a, int target) {
    int i = 0, j = a.length;
    while (1 < j - i) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m;
        } else {
            i = m;
        }
    }
    return (a[i] == target) ? i : -1;
}

这个版本就像是一个追求完美平衡的瑜伽大师:

使用左闭右开区间,就像瑜伽动作中的”半莲花坐”。
不急于一次找到目标,而是慢慢缩小范围,就像瑜伽中的”渐进式放松”。
移动边界时保持谨慎,不错过任何可能性,就像瑜伽中的”正念观察”。
平均比较次数减少,效率提高,就像熟练的瑜伽师动作更加流畅。
时间复杂度保持在 $Θ (l o g (n))$ ,稳如泰山。

Java 版: 官方认证的二分查找

返回负数表示没找到,但这个负数还能告诉你往哪插入新元素。这就像是一个聪明的图书管理员,不仅告诉你书不在架上,还指出应该放在哪个位置。

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
    int low = fromIndex;
    int high = toIndex - 1;
 
    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];
 
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

这个版本就像是Java世界的”官方认证二分查找大师”，它有几个独特的特点:

灵活的搜索范围: 通过fromIndex和toIndex参数，你可以在数组的任意部分进行搜索。这就像是
聪明的返回值：
- 如果找到目标，直接返回索引。简单明了。
- 如果没找到，返回-(low + 1)。这个设计非常巧妙：
  - 负数表示没找到，保持了与找到时返回正数的区分。
  - low表示应插入的位置，加1是为了处理应插入位置为0的特殊情况。
  - 取负是为了与找到的情况区分。
插入点的妙用：
- 例如，对于数组[1,3,5,6]要插入2，循环结束后low的值就是2应该插入的位置。
- 这个特性使得这个方法不仅可以用于查找，还可以用于确定插入新元素的正确位置，一举两得。
位运算优化：使用>>>（无符号右移）来计算中间位置，这是一个经典的性能优化技巧。

Leftmost 与 Rightmost：精确定位

Leftmost 版本

public static int binarySearchLeftmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target <= a[m]) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return i; 
}

Rightmost 版本

public static int binarySearchRightmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return i - 1;
}

这两个版本的应用简直就是算法界的瑞士军刀:

可以用来查找范围,就像在图书馆中找特定年代的书。
可以用来求排名,就像在运动会上确定选手的名次。
可以找前任后任,就像在族谱中寻找长辈晚辈。
甚至可以找最近邻居,就像在社交网络中寻找最相似的人。

🪴 Quartz 4.0

Explorer

算法初识

算法初识

算法: 程序员的致胜法宝

定义

理解

数据结构: 程序员的积木游戏

定义

理解

二分查找: 程序员的”猜数字”游戏

基础版：最简单的”猜数字”游戏

Java实现

改进版

为什么用右移而不是除以2?

衡量算法好坏

线性查找

二分查找：F1赛车

性能对比：家用车 vs F1赛车

时间复杂度

大O表示法

如何简化到大O

常见的时间复杂度

渐进界限

空间复杂度

二分查找的空间复杂度

二分查找的性能分析

时间复杂度

空间复杂度: $O (1)$

再看二分查找

平衡版：追求完美平衡

Java 版: 官方认证的二分查找

Leftmost 与 Rightmost：精确定位

Leftmost 版本

Rightmost 版本

Graph View

Table of Contents

Backlinks

🪴 Quartz 4.0

Explorer

算法初识

算法初识

算法: 程序员的致胜法宝

定义

理解

数据结构: 程序员的积木游戏

定义

理解

二分查找: 程序员的”猜数字”游戏

基础版：最简单的”猜数字”游戏

Java实现

改进版

为什么用右移而不是除以2?

衡量算法好坏

线性查找

二分查找：F1赛车

性能对比：家用车 vs F1赛车

时间复杂度

大O表示法

如何简化到大O

常见的时间复杂度

渐进界限

空间复杂度

二分查找的空间复杂度

二分查找的性能分析

时间复杂度

空间复杂度: O(1)

再看二分查找

平衡版：追求完美平衡

Java 版: 官方认证的二分查找

Leftmost 与 Rightmost：精确定位

Leftmost 版本

Rightmost 版本

Graph View

Table of Contents

Backlinks

空间复杂度: $O (1)$