C++数组与链表解析：力扣刷题心得

“力扣刷题集-更新至链表” 这篇资源主要涵盖了数组和链表这两种数据结构在编程中的应用，特别提到了C++和Java的相关知识，以及二分查找算法。以下是这些知识点的详细说明： 1. **数组**： - 数组是一种基本的数据结构，它将相同类型的数据元素存储在连续的内存空间中，便于通过下标访问。 - 数组的元素不能直接删除，只能通过覆盖来“删除”某个元素。一旦数组创建，其大小固定，无法动态扩展或收缩。 - 在C++中，`sort()`函数可以用于对数组进行排序，`reverse()`可以用来反转数组元素的顺序。 - C++的`vector`是动态数组，底层实现基于数组，但提供了更多的功能，如动态增长和缩小，而`array`则是一个固定大小的数组。 - 在二维数组中，元素在内存中是连续分布的，行间地址间隔通常是元素大小乘以行数。 2. **C++中的vector与array的区别**： - `vector`是STL容器之一，支持动态增长和收缩，提供插入、删除等操作，而`array`是C++11引入的，是一个固定大小的数组，更接近于C风格的数组。 3. **Java中的二分查找**： - 二分查找适用于有序且无重复元素的数组，它可以在对数时间内找到目标值的索引，效率高。 - 在二分查找中，区间通常定义为左闭右闭或左闭右开，根据不同的条件更新查找范围。 - 二分查找的基本步骤包括设定左右边界，计算中间值，比较中间值与目标值，并根据比较结果调整查找范围。 4. **链表**： - 虽然题目描述中没有详细展开链表，但链表是另一个重要的数据结构，与数组相比，链表的元素在内存中不必连续，通过指针链接各个节点，插入和删除操作通常更快，但访问元素的速度较慢，因为需要遍历。 5. **二分查找算法的适用场景**： - 二分查找通常用于解决查找问题，例如在有序列表中寻找特定元素，或者在有序数据中进行插值搜索等。 - 题目示例中给出的704题是二分查找的一个典型应用，要求在一个有序整数数组中查找目标值并返回其下标。 6. **二分查找的优化**： - 在实际应用中，二分查找可能会遇到重复元素的情况，此时可以考虑记录查找过程中出现的多个匹配元素的索引，或者对查找方法进行微调，以处理重复值。 这些知识对于学习算法和数据结构，特别是准备面试或刷题（如LeetCode）的程序员来说非常重要。理解并熟练运用数组、链表和二分查找等基础概念，是提升编程技能的关键步骤。