黑马数据结构讲义

JavaJuice约 8570 字大约 29 分钟

011-如何衡量算法好坏-3

算法性能分析课程文档（修订版）

二、空间复杂度

定义
• 空间复杂度用于衡量算法在运行过程中占用额外空间（非原始数据空间）的增长趋势

• 使用大O表示法进行量化，关注随着数据规模n增大时额外空间的增长趋势

• 关键概念：额外空间指算法运行所需存储空间，不包含原始输入数据占用的空间

示例分析（二分查找算法）

# 伪代码示例
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

空间占用分析：

固定空间占用：
• 指针变量：left（4字节）、right（4字节）、mid（4字节）
• 总固定空间：3×4 = 12字节（与数据规模无关）
空间特性：
• 循环变量mid在每次迭代中复用存储空间
• 不会随着数组规模(n)的增大而增加额外空间

空间复杂度结论：
• O(1)（常数阶空间复杂度）

三、二分查找综合性能分析

时间复杂度

情况类型	时间复杂度	说明
最坏情况	O(log n)	元素不存在或位于最终分区
最好情况	O(1)	目标元素正好位于中间位置
平均情况	O(log n)	数学推导结果（未展示推导过程）

空间复杂度
• O(1)（恒定额外空间）

• 仅需存储三个指针变量（left/right/mid）

重要补充说明
大O表示法特性：
• 忽略常数项、系数和低阶项
• 关注最高阶项的增长趋势
紧致界限（Θ表示法）不适用情况：
• 由于最好情况(O(1))与最坏情况(O(log n))无法用统一函数表示
• 因此不适合使用Θ表示法描述整体时间复杂度
空间复杂度计算原则：
• 仅计算算法运行需要的额外存储空间
• 不包含输入数据本身的存储空间

四、核心概念总结

时间复杂度与空间复杂度共同构成算法效率评价体系
二分查找算法优势：
• 时间效率：对数级时间复杂度显著优于线性查找
• 空间效率：恒定空间复杂度，适合大规模数据处理
算法选择原则：需根据具体场景在时间与空间开销之间进行权衡

（文档结束）

012-二分查找-平衡版

改进版二分查找算法详解

一、问题背景与经典算法分析
1.1 传统二分查找的局限性
在标准二分查找算法中，当目标元素位于数组最左侧时，每次循环只需执行一次比较（if条件成立）；而当目标元素位于最右侧时，每次循环需要执行两次比较（if不成立后进入else if）。这种不平衡性导致：

• 最左元素查找：循环次数 L 次 → 总比较次数 L 次

• 最右元素查找：循环次数 L 次 → 总比较次数 2L 次

1.2 经典算法伪代码示例

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if target < arr[mid]:
            right = mid - 1
        elif target > arr[mid]:
            left = mid + 1
        else:
            return mid
    return -1

二、改进算法设计原理
2.1 核心改进思路
• 平衡比较次数：消除else if分支，保证每次循环仅执行一次条件判断

• 延迟最终判断：将目标元素的最终匹配检查移至循环外

• 区间定义调整：采用左闭右开区间 [i, j)，保证边界处理的统一性

2.2 关键实现细节
区间定义
• i指针：指向可能的候选元素

• j指针：指向非候选元素的右边界

• 有效区间：[i, j)，包含 j-i 个待查元素

循环终止条件
while j - i > 1:
当区间内元素数量 >1 时继续循环，最终保证区间内只剩 0 或 1 个元素

三、改进算法完整实现

def balanced_binary_search(arr, target):
    i, j = 0, len(arr)
    while j - i > 1:
        mid = (i + j) // 2
        if target < arr[mid]:
            j = mid  # 右边界收缩至mid（保持开区间）
        else:
            i = mid  # 左边界扩展至mid（包含可能目标）
    return i if arr[i] == target else -1

四、算法关键步骤解析
4.1 边界收缩逻辑

条件	操作	说明
`target < arr[mid]`	`j = mid`	目标在左半区，保持i不变
`target >= arr[mid]`	`i = mid`	目标在右半区或等于中间值

4.2 循环终止时的状态
• 最终区间：[i, j) 且 j = i + 1

• 唯一候选：仅剩 arr[i] 需要验证

• 最终验证：循环外检查 arr[i] == target

五、复杂度分析
5.1 时间复杂度对比

算法版本	最好情况	最坏情况	平均情况
传统算法	O(1)	O(log n)	O(log n)
改进算法	Θ(log n)	Θ(log n)	Θ(log n)

5.2 改进算法的优势
• 比较次数平衡：每次循环固定执行1次比较

• 稳定时间复杂度：消除最好情况下的O(1)

• 边界处理统一：避免±1的边界错误

六、应用场景建议
• 大型数据集：数据规模越大，平衡比较次数的优势越明显

• 均匀分布数据：适合需要稳定性能表现的场景

• 嵌入式系统：可预测的时间复杂度更适合实时系统

七、算法可视化示例

初始数组: [10, 20, 30, 40, 50, 60, 70, 80]
查找目标: 20

迭代过程：
1. [10,20,30,40 | 50,60,70,80] mid=3(40)
   20 < 40 → j=3
2. [10,20 | 30,40] mid=1(20)
   20 >=20 → i=1
3. 循环终止(i=1, j=2)
验证arr[1]=20 → 查找成功

八、扩展思考

重复元素处理：如何修改算法返回第一个/最后一个匹配项？
动态数组优化：如何应对数据插入/删除频繁的场景？
多维度扩展：如何将算法应用于二维有序矩阵的搜索？

该改进算法通过统一比较次数和优化边界处理，在保证对数时间复杂度的同时提高了算法稳定性，特别适合需要稳定性能表现的大规模数据应用场景。

013-二分查找-Java版

Java二分查找实现详解

一、Arrays类中的二分查找方法

方法位置
位于java.util.Arrays类中，包含多个重载方法：

public static int binarySearch(int[] a, int key)
public static int binarySearch(long[] a, int fromIndex, int toIndex, long key)
// 其他基本类型数组的类似方法

核心实现（int数组版本）

public static int binarySearch(int[] a, int key) {
    return binarySearch0(a, 0, a.length, key);
}

private static int binarySearch0(int[] a, int low, int high, int key) {
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // 找到目标值
    }
    return -(low + 1); // 未找到时的返回值
}

二、返回值解析

找到目标值
• 返回目标值在数组中的索引（0-based）
未找到目标值
• 返回值为负数，格式：-(insertionPoint + 1)

• 插入点计算：

int insertionPoint = -(returnValue + 1);

示例说明

int[] arr = {2, 5, 8};

// 查找存在的元素
System.out.println(Arrays.binarySearch(arr, 5));  // 输出1

// 查找不存在的元素
System.out.println(Arrays.binarySearch(arr, 4));   // 输出-2（插入点1）
System.out.println(Arrays.binarySearch(arr, 1));   // 输出-1（插入点0）
System.out.println(Arrays.binarySearch(arr, 9));   // 输出-4（插入点3）

三、插入点处理实践

插入元素到有序数组

int[] insert(int[] original, int target) {
    int index = Arrays.binarySearch(original, target);

    if (index >= 0) return original; // 元素已存在

    // 计算实际插入位置
    int insertionPoint = -index - 1;
    int[] newArr = new int[original.length + 1];

    // 拷贝前半部分
    System.arraycopy(original, 0, newArr, 0, insertionPoint);

    // 插入新元素
    newArr[insertionPoint] = target;

    // 拷贝后半部分
    System.arraycopy(original, insertionPoint, newArr, insertionPoint + 1,
                    original.length - insertionPoint);

    return newArr;
}

使用示例

int[] arr = {2, 5, 8};
int[] result = insert(arr, 4);
System.out.println(Arrays.toString(result)); // 输出[2, 4, 5, 8]

四、实现细节解析

边界处理
• 初始边界：low=0, high=length-1
• 循环条件：while (low <= high) 保证最后一次比较
中间值计算
• 使用无符号右移：(low + high) >>> 1
• 避免整数溢出问题
比较顺序
• 先判断中间值是否小于目标值（向右查找）
• 再判断中间值是否大于目标值（向左查找）
返回值设计
• 负数保证与成功查找区分
• +1操作避免插入点0与成功查找混淆

五、扩展应用

对象数组版本
需要传入Comparator进行自定义比较：

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

范围查找

int[] arr = {1,3,5,7,9};
// 在[2,4)索引范围查找
Arrays.binarySearch(arr, 2, 4, 6);

实际应用场景
• 维护有序数据集
• 快速查找最近元素
• 范围查询优化

六、性能注意事项

时间复杂度：O(log n)
前置条件：数组必须已排序
当需要频繁插入时，建议使用更高效的数据结构（如TreeSet）

014-二分查找-LeftRightmost

二分查找算法对重复元素的处理优化

一、基础版二分查找的问题
示例数组
[1, 2, 3, 4, 4, 4, 5, 6, 7] 包含重复元素4

基础算法表现
当查找重复元素时（如4），基础算法会返回第一个遇到的中间元素：

中间索引计算方式：mid = (low + high) // 2
示例中首次定位到索引3的4即返回
无法保证返回最左侧/最右侧的重复元素

二、Leftmost 最左侧元素查找
算法改进思路

新增候选变量candidate记录可能的最左位置
当中间元素等于目标值时：
• 记录当前中间位置
• 继续在左半区间[low, mid-1]查找

代码实现

def binary_search_leftmost(arr, target):
    low = 0
    high = len(arr) - 1
    candidate = -1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] > target:
            high = mid - 1
        else:
            candidate = mid  # 记录候选位置
            high = mid - 1   # 继续向左查找

    return candidate

执行流程（以查找4为例）

初始范围[0,8]，mid=4（值4）→ 记录candidate=4，缩小右边界到3
新范围[0,3]，mid=1（值2）→ 调整左边界到2
新范围[2,3]，mid=2（值3）→ 调整左边界到3
范围[3,3]，mid=3（值4）→ 更新candidate=3，继续向左查找
最终返回candidate=2（实际最左侧4的位置）

三、Rightmost 最右侧元素查找
算法改进思路

同样使用候选变量candidate
当中间元素等于目标值时：
• 记录当前中间位置
• 继续在右半区间[mid+1, high]查找

代码实现

def binary_search_rightmost(arr, target):
    low = 0
    high = len(arr) - 1
    candidate = -1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] > target:
            high = mid - 1
        else:
            candidate = mid  # 记录候选位置
            low = mid + 1    # 继续向右查找

    return candidate

执行流程（以查找4为例）

初始范围[0,8]，mid=4（值4）→ 记录candidate=4，调整左边界到5
新范围[5,8]，mid=6（值5）→ 调整右边界到5
范围[5,5]，mid=5（值4）→ 更新candidate=5，继续向右查找
最终返回candidate=5（实际最右侧4的位置）

四、测试用例验证
测试数组
[1, 2, 3, 4, 4, 4, 5, 6, 7]

测试结果

目标值	leftmost结果	rightmost结果
1	0	0
4	3	5
5	6	6
8	-1	-1

五、算法特性

时间复杂度：O(log n)
空间复杂度：O(1)
核心改进点：
• 发现匹配元素不立即返回
• 通过边界调整继续搜索
• 候选变量记录最新可能结果

六、应用场景

统计元素出现次数（rightmost - leftmost + 1）
有序集合中确定元素的边界位置
处理需要模糊匹配的场景（如数值范围查询）

015-二分查找-LeftRightmost-返回值

二分查找进阶：LeftMost与RightMost优化版本详解

一、基础版本回顾

LeftMost基础版
• 功能：查找与目标值相等的最左索引

• 返回值：找到返回索引，未找到返回-1

RightMost基础版
• 功能：查找与目标值相等的最右索引

• 返回值：找到返回索引，未找到返回-1

二、优化改进思路
传统返回-1的局限性：
• 无法提供插入位置参考

• 未充分利用查找过程中的边界信息

三、LeftMost优化版实现

代码改进点

public static int leftMost2(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; // 关键改动
}

返回值含义
查找情况返回值意义示例说明
目标存在等于目标的最左索引查找4返回索引3
目标不存在第一个大于目标的索引（插入位置）查找3返回索引4
核心特性
• 数学表达：返回首个≥target的位置索引

查找情况	返回值意义	示例说明
目标存在	等于目标的最左索引	查找4返回索引3
目标不存在	第一个大于目标的索引（插入位置）	查找3返回索引4

• 边界处理：当i超过数组长度时，说明所有元素都小于目标

四、RightMost优化版实现

代码改进点

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

返回值含义
查找情况返回值意义示例说明
目标存在等于目标的最右索引查找4返回索引5
目标不存在最后一个小于目标的索引查找5返回索引4
核心特性
• 数学表达：返回最后一个≤target的位置索引

查找情况	返回值意义	示例说明
目标存在	等于目标的最右索引	查找4返回索引5
目标不存在	最后一个小于目标的索引	查找5返回索引4

• 边界处理：当i == 0时，说明所有元素都大于目标

五、应用场景对比

版本	适用场景	典型应用
LeftMost2	插入位置查找/范围起始点确定	维护有序集合插入位置
RightMost2	存在性验证/范围结束点确定	统计元素出现次数

六、复杂度分析
• 时间复杂度：O(log n)

• 空间复杂度：O(1)

• 循环次数：最多⌈log₂(n+1)⌉次

七、验证示例
假设数组为[1, 3, 4, 4, 7, 8, 9]

LeftMost2测试
• 查找4 → 返回2（正确的最左索引）

• 查找5 → 返回4（插入位置应在7前）

RightMost2测试
• 查找4 → 返回3（正确的最右索引）

• 查找5 → 返回3（最后一个小于5的元素）

八、实现要点总结

循环条件：始终保持i <= j确保完整搜索区间
中间值计算：使用无符号右移(i + j) >>> 1防止整数溢出
边界收缩：每次循环至少排除1个元素保证终止性
返回值修正：RightMost需i-1补偿最后一次右移

附：边界值测试建议
• 空数组处理

• 单元素数组

• 全相同元素数组

• 目标值小于所有元素

• 目标值大于所有元素

016-二分查找-LeftRightmost-应用

以下是经过校正整理的课程文档：

二分查找进阶应用详解

核心概念
• Leftmost：查找第一个≥target的元素位置

• Rightmost：查找最后一个≤target的元素位置

核心应用场景

一、求排名（Rank）
定义：计算target在有序数组中的排序位置（从1开始计数）

公式：

rank = leftmost(target) + 1

示例：
数组：[1, 2, 4, 4, 4, 5, 6, 7, 7]
• 元素5的排名：leftmost(5)=5 → 5+1=6

• 元素4的排名：leftmost(4)=2 → 2+1=3

二、求前驱（Predecessor）
定义：比target小的最大元素（最接近的较小值）

公式：

predecessor = leftmost(target) - 1

示例：
• 5的前驱：leftmost(5)=5 → 5-1=4（元素4）

• 4的前驱：leftmost(4)=2 → 2-1=1（元素2）

三、求后继（Successor）
定义：比target大的最小元素（最接近的较大值）

公式：

successor = rightmost(target) + 1

示例：
• 5的后继：rightmost(5)=5 → 5+1=6（元素6）

• 4的后继：rightmost(4)=4 → 4+1=5（元素5）

四、最近邻（Nearest Neighbor）
定义：前驱和后继中更接近target的元素

判断方法：

分别找出前驱和后继
比较两者与target的差值
取差值更小的元素

五、范围查询

基础范围
查询条件公式
x < target [0, leftmost(target)-1]
x ≤ target [0, rightmost(target)]
x > target [rightmost(target)+1, ∞]
x ≥ target [leftmost(target), ∞]
复合范围
示例：查询4 ≤ x ≤ 7

查询条件	公式
x < target	[0, leftmost(target)-1]
x ≤ target	[0, rightmost(target)]
x > target	[rightmost(target)+1, ∞]
x ≥ target	[leftmost(target), ∞]

范围 = [leftmost(4), rightmost(7)]

示例：查询4 < x < 7

范围 = [rightmost(4)+1, leftmost(7)-1]

实现要点

索引转换：所有计算结果需根据编程语言的索引规则调整（0-based/1-based）
边界处理：特别注意数组越界情况
重复元素：leftmost/rightmost能正确处理重复元素
不存在元素：当target不存在时，仍可通过前驱/后继公式找到正确位置

应用场景扩展
• 排行榜系统

• 数值区间统计

• 最近值查找（如温度最接近的传感器数据）

• 数据库范围查询优化

通过掌握这些二分查找的进阶用法，可以高效解决有序数据集合中的多种查询问题，时间复杂度始终保持在O(log n)。

017-二分查找-e01-二分查找

LeetCode 704 二分查找算法详解

题目要求
给定一个升序排列的整数数组 nums 和一个目标值 target，实现二分查找算法。若目标值存在则返回下标，否则返回 -1。

示例
• 输入：nums = [-1,0,3,5,9,12], target = 9 → 输出：4

• 输入：nums = [-1,0,3,5,9,12], target = 2 → 输出：-1

算法实现详解

一、基础版二分查找（闭区间）
核心思路
• 搜索区间：[i, j]（包含两端点）

• 循环条件：i <= j（保证最后一次元素比较机会）

• 边界调整：

• target < nums[m] → 左区间 j = m - 1

• target > nums[m] → 右区间 i = m + 1

代码实现

public int search(int[] nums, int target) {
    int i = 0, j = nums.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1; // 无符号右移避免溢出
        if (target < nums[m]) {
            j = m - 1;
        } else if (target > nums[m]) {
            i = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

关键点

循环条件中的等号保证单个元素的比较机会
中间值计算采用无符号右移实现防溢出除法
每次调整边界时排除已比较元素

二、改动版二分查找（左闭右开区间）
核心思路
• 搜索区间：[i, j)（j指向元素不参与比较）

• 循环条件：i < j（i=j时区间无元素）

• 边界调整：

• target < nums[m] → 左区间 j = m

• target > nums[m] → 右区间 i = m + 1

代码实现

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

关键改进

初始右边界设为数组长度
右边界调整时直接赋值为中间值
减少循环次数但保持逻辑等价性

三、平衡版二分查找（优化比较次数）
核心思路
• 搜索区间：[i, j)（同改动版）

• 每次循环仅比较一次

• 最终在循环外验证结果

• 循环条件：j - i > 1（保证最终剩余1个元素）

代码实现

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

核心优化

每次循环仅执行一次比较操作
边界调整时保留潜在匹配元素
最终验证确保不漏判

性能对比

版本	时间复杂度	空间复杂度	平均比较次数
基础版	O(log n)	O(1)	log2n
改动版	O(log n)	O(1)	log2n
平衡版	O(log n)	O(1)	log2(n)+1

注意事项

所有版本均需处理数组长度为0的边界情况
中间值计算建议使用无符号右移代替除法
元素唯一性保证简化了算法实现
最终测试结果均为0ms（Java实现）

总结
三种实现方式在时间复杂度上等价，主要差异体现在：

边界条件的处理方式
比较次数的优化策略
代码的可维护性

建议根据实际需求选择：
• 基础版：最易理解的实现方式

• 改动版：更清晰的区间定义

• 平衡版：追求极致的性能优化

017-二分查找-e02-搜索插入位置

力扣第35题 - 搜索插入位置题解

题目描述
给定一个升序排列的整数数组 nums 和一个目标值 target，要求：
• 若 target 存在于数组中，返回其索引

• 若 target 不存在于数组中，返回其按顺序插入的位置（插入后数组仍保持升序）

示例
输入：nums = [1,3,5,6], target = 5 → 输出：2
输入：nums = [1,3,5,6], target = 2 → 输出：1
输入：nums = [1,3,5,6], target = 7 → 输出：4

约束条件
• 时间复杂度需为 O(log n)

• 数组元素无重复

解题思路分析

方法一：标准二分查找改进
核心思想
基于标准二分查找框架，最终返回左指针 low，该指针在查找失败时会自然指向插入位置。

算法步骤

初始化指针：low = 0，high = nums.length - 1
循环直到 low > high：
• 计算中间索引 mid = (low + high) / 2
• 若 nums[mid] < target，说明目标在右半区 → low = mid + 1
• 否则，目标在左半区或等于中间值 → high = mid - 1
返回 low（即插入位置）

代码实现

public int searchInsert(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

复杂度分析
• 时间复杂度：O(log n)

• 空间复杂度：O(1)

方法二：Leftmost二分查找
核心思想
处理更通用的场景（含重复元素），寻找第一个大于等于目标值的索引位置，该位置即为插入点。

算法步骤

初始化指针：i = 0，j = nums.length - 1
循环直到 i > j：
• 计算中间索引 mid = (i + j) / 2
• 若 nums[mid] >= target，继续向左搜索 → j = mid - 1
• 若 nums[mid] < target，向右搜索 → i = mid + 1
返回 i（即第一个≥target的位置）

代码实现

public int searchInsert(int[] nums, int target) {
    int i = 0, j = nums.length - 1;
    while (i <= j) {
        int mid = (i + j) >>> 1;
        if (nums[mid] >= target) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    return i;
}

复杂度分析
• 时间复杂度：O(log n)

• 空间复杂度：O(1)

关键点说明

循环终止条件：当 low > high（或 i > j）时，low（或 i）即为插入位置
插入位置特性：插入位置是数组中第一个大于等于目标值的元素索引
重复元素处理：方法二可正确处理含重复元素的场景（返回最左插入点）

两种方法均满足题目时间复杂度要求，且能正确处理无重复元素的升序数组场景。方法二具有更强的通用性，推荐掌握其思想以应对更复杂的变种问题。

017-二分查找-e03-搜索开始结束位置

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

题目描述
给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target。要求找出目标值在数组中的开始位置和结束位置。若目标值不存在于数组中，返回 [-1, -1]。算法时间复杂度需为 O(log n) 级别。

示例
输入：
nums = [5,7,7,8,8,10], target = 8
输出：
[3,4]
解释：
数字 8 在数组中首次出现于索引 3，最后出现于索引 4。

解题思路
使用二分查找的两个变种：

寻找左边界（Left Most）：找到第一个等于 target 的元素。
寻找右边界（Right Most）：找到最后一个等于 target 的元素。

左边界查找逻辑
• 当中间值等于 target 时，记录候选位置并继续向左搜索。

• 中间值大于等于 target 时，向左调整右边界。

• 中间值小于 target 时，向右调整左边界。

右边界查找逻辑
• 当中间值等于 target 时，记录候选位置并继续向右搜索。

• 中间值小于等于 target 时，向右调整左边界。

• 中间值大于 target 时，向左调整右边界。

代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = findLeft(nums, target);
        if (left == -1) {
            return new int[]{-1, -1};
        }
        int right = findRight(nums, target);
        return new int[]{left, right};
    }

    private int findLeft(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if (nums[m] > target) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    private int findRight(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if (nums[m] > target) {
                j = m - 1;
            } else if (nums[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }
}

复杂度分析
• 时间复杂度：O(log n)

两次二分查找分别耗时 O(log n)。
• 空间复杂度：O(1)

仅使用常数级别的额外空间。

关键点说明

循环条件：i <= j 保证所有元素被遍历。
中间值计算：使用 i + (j - i) / 2 避免整数溢出。
候选值更新：找到目标值时更新候选值，并根据方向调整边界。
合并结果：若左边界未找到，直接返回 [-1, -1]；否则合并左右边界结果。

注意事项
• 数组为空时直接返回 [-1, -1]。

• 目标值不存在时，候选值保持初始值 -1。

018-数组-概述

数据结构课程文档：数组详解

一、数组定义
数组（Array）是由一组相同类型元素组成的数据结构，具有以下核心特性：

元素统一性：所有元素必须为同一数据类型（如int、double等），不允许混合类型
索引标识：每个元素通过唯一索引（Index）或键（Key）标识，索引通常从0开始编号
集中管理：多个元素通过单一数据结构进行统一管理

二、核心特点

连续存储
• 内存中元素按顺序连续存储

• 存储地址计算公式：元素地址 = 基地址(base address) + 索引(I) × 元素大小(size)

• 示例分析：

int数组[1,2,3,4,5]
基地址：0x4C8
元素3（索引2）地址 = 0x4C8 + 2×4 = 0x4D0

地址计算原理
元素索引地址计算 16进制结果
元素1 0 0x4C8 + 0×4 = 0x4C8 0x4C8
元素2 1 0x4C8 + 1×4 = 0x4CC 0x4CC
元素3 2 0x4C8 + 2×4 = 0x4D0 0x4D0

元素	索引	地址计算	16进制结果
元素1	0	0x4C8 + 0×4 = 0x4C8	0x4C8
元素2	1	0x4C8 + 1×4 = 0x4CC	0x4CC
元素3	2	0x4C8 + 2×4 = 0x4D0	0x4D0

三、空间占用分析（以Java为例）

内存结构

组成部分	大小（字节）	说明
Mark Word	8	存储哈希码、GC信息、锁状态等
类指针	4	指向数组类型的Class对象
数组长度	4	记录数组容量（最大2^32-1）
元素存储区	n×size	实际数据存储区域
对齐填充	0-7	保证总大小为8的倍数

示例分析
int数组[1,2,3,4,5]内存分布：

对象头（16字节）
元素存储区（5×4=20字节）
对齐填充（4字节）
总大小：16+20+4=40字节

四、性能特性

随机访问
• 时间复杂度：O(1)

• 实现原理：通过索引直接计算物理地址

• 优势：访问时间与数据规模无关

空间效率
数据类型元素大小 10万元素占用空间
int 4字节 ~400KB
double 8字节 ~800KB

数据类型	元素大小	10万元素占用空间
int	4字节	~400KB
double	8字节	~800KB

五、应用限制

固定容量：传统数组创建后容量不可变
类型约束：严格限制元素类型一致性
插入/删除：需要移动后续元素（后续动态数组解决）

六、关键概念对比

术语	说明	常见翻译
Index	基于偏移量的位置标识	索引
Key	可自定义的标识符	键
Base Address	数组首元素的内存起始地址	基地址

下节预告
动态数组（ArrayList）实现原理：
• 容量自动扩展机制

• 插入/删除操作优化

• 时间复杂度分析

注：本文档已校正原始录音中的术语错误（如"贱"->"键"），并优化技术表述的准确性。

019-动态数组-介绍

动态数组课程文档

一、静态数组的局限性

固定容量：Java原生数组在创建时需指定固定大小，后期无法修改
功能限制：不支持元素的插入和删除操作
内存管理：无法根据实际使用需求自动调整存储空间

二、动态数组的引入

核心特性
• 动态扩容：容量根据元素数量自动调整

• 元素操作：支持插入、删除等动态操作

• 逻辑管理：通过size属性控制有效元素范围

Java实现基础
• Java标准库中的ArrayList是典型动态数组实现

• 本课程目标：手动实现动态数组底层逻辑

三、动态数组核心机制

核心属性说明
属性名类型作用描述初始值
size int 记录有效元素个数（逻辑大小） 0
capacity int 当前数组容量（物理大小） 8
elements[] int[] 底层数据存储结构 new int[8]
功能演示案例
添加元素流程
初始状态：size=0，capacity=8
添加元素1-5：
• 每次添加size递增
• 元素依次存入elements[0]-elements[4]
• 最终size=5，capacity保持8

属性名	类型	作用描述	初始值
size	int	记录有效元素个数（逻辑大小）	0
capacity	int	当前数组容量（物理大小）	8
elements[]	int[]	底层数据存储结构	new int[8]

删除元素流程（删除索引2的元素）

元素前移：将elements[3]-elements[4]前移一位
size递减：size从5变为4
最终结果：[1,2,4,5]

扩容机制演示

当添加第9个元素时：
• 检测size+1 > capacity
• 创建新数组（容量为原1.5倍，示例为12）
• 旧数组元素全部复制到新数组
• 更新capacity属性值
• 完成新增元素操作

四、动态数组类实现框架

类结构设计

public class DynamicArray {
    // 底层存储结构
    private int[] elements;
    // 逻辑大小
    private int size = 0;
    // 初始容量
    private static final int INITIAL_CAPACITY = 8;

    // 构造方法
    public DynamicArray() {
        this.elements = new int[INITIAL_CAPACITY];
    }
}

待实现功能列表
插入元素（指定位置）
删除元素（指定位置）
自动扩容机制
动态缩容机制（可选）
元素遍历方法
容量查询接口

五、核心算法说明

时间复杂度对比
操作静态数组动态数组
随机访问 O(1) O(1)
头部插入 N/A O(n)
尾部插入 N/A 平均O(1)
指定位置插入 N/A O(n)
扩容操作 N/A O(n)
扩容策略优化
• 扩容因子：建议使用1.5倍扩容（平衡空间和时间效率）

操作	静态数组	动态数组
随机访问	O(1)	O(1)
头部插入	N/A	O(n)
尾部插入	N/A	平均O(1)
指定位置插入	N/A	O(n)
扩容操作	N/A	O(n)

• 缩容机制：当size < capacity/4时进行缩容（避免内存浪费）

• 批量操作：预先估计需要容量，减少扩容次数

六、学习要点总结

理解size和capacity的双重管理机制
掌握元素移动的核心算法（System.arraycopy）
熟悉数组扩容的标准实现流程
注意数组索引越界的边界条件处理
了解时间复杂度的分析方法

注：本实现以int数组为例进行说明，实际应用中可通过泛型改造支持多种数据类型。Java标准库的ArrayList使用Object[]数组配合类型擦除机制实现泛型支持。

020-动态数组-插入

动态数组功能实现文档

功能一：addLast 方法实现
功能描述
向动态数组末尾添加新元素，新增元素始终作为数组最后一个元素

实现逻辑

索引计算
新元素插入位置 = 当前数组长度(size)
• 初始空数组(size=0)时插入位置0
• 已有元素时插入位置为当前最后一个元素的索引+1
核心代码

public void addLast(int element) {
    array[size] = element;  // 将新元素放入size位置
    size++;                 // 数组长度+1
}

调用示例

// 添加顺序：1 → 2 → 3 → 4 → 5
addLast(1);  // array[0]=1, size=1
addLast(2);  // array[1]=2, size=2

功能二：add 方法实现
功能描述
向指定索引位置插入新元素，后续元素依次后移

实现逻辑

参数验证
• 有效索引范围：0 ≤ index ≤ size
• 非法索引处理：抛出异常或返回错误提示
元素移动
使用System.arraycopy进行数组内元素拷贝：

System.arraycopy(
    array,      // 源数组
    index,      // 起始拷贝位置
    array,      // 目标数组（相同数组）
    index + 1,  // 目标起始位置（后移一位）
    size - index // 需要移动的元素个数
);

插入元素

array[index] = element;  // 插入新元素
size++;                   // 数组长度+1

完整代码

public void add(int index, int element) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("非法索引: " + index);
    }

    // 元素后移操作
    System.arraycopy(array, index, array, index + 1, size - index);

    array[index] = element;
    size++;
}

方法重载优化
将addLast整合为add方法的特例：

public void addLast(int element) {
    add(size, element);  // 直接调用通用add方法
}

关键处理说明

边界条件
• index=size时等效addLast
• index=0时所有元素后移（头部插入）
时间复杂度
• 最优：O(1)（末尾插入）
• 最差：O(n)（头部插入）
扩容机制
（注：本文档未包含扩容实现，实际使用时需确保数组容量足够）

使用示例

// 初始数组：[1, 2, 3, 4, 5]
add(2, 6);  // 在索引2插入6

// 执行过程：
1. 元素3、4、5后移 → [1, 2, _, 3, 4, 5]
2. array[2] = 6     → [1, 2, 6, 3, 4, 5]
3. size从5变为6

注意事项

插入操作前必须验证索引有效性
需考虑数组容量不足时的自动扩容机制
批量插入时建议先扩容至目标尺寸再进行操作
元素类型可根据需求泛型化（本文以int类型为例）