一、数据结构基本介绍

定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。简单来说，就是“带结构”的数据元素的集合。

重要性：数据结构是计算机类专业的核心基础课程之一，是算法分析与设计、操作系统、数据库、人工智能等课程的基础，也是企业笔试、面试和研究生入学考试的重要内容。

1. 逻辑结构（数据之间的逻辑关系）

这是从抽象思维层面看待数据，独立于计算机硬件。主要分为四类：

• 集合：数据之间“同属一个集体”，无其他特殊关系（如数学中的集合）。

• 线性结构：数据之间存在“一对一”的关系。典型代表：数组、链表、栈、队列。

• 树形结构：数据之间存在“一对多”的层次关系。典型代表：二叉树、堆、B树（常用于文件系统和数据库索引）。

• 图形结构：数据之间存在“多对多”的复杂关系。典型代表：有向图、无向图（常用于社交网络、地图导航）。

2. 物理结构（数据在计算机内存中的存储）

这是从具体实现层面看待数据，决定数据如何在内存中安家。主要有两种：

• 顺序存储：数据存放在连续的内存地址中（如数组）。优点是寻址快（通过下标O(1)访问）；缺点是插入和删除慢（需要移动大量元素），且容易造成内存碎片。

• 链式存储：数据存放在任意的内存地址中，通过“指针”串联（如链表）。优点是插入和删除快（只需修改指针）；缺点是访问慢（需要从头遍历），且需要额外空间存储指针。

二、数组基本概念

• 定义：数组是由 n（n ≥ 1）个相同类型的数据元素 构成的有限序列，逻辑表示为：
  A = (a₁, a₂, …, aₙ)

• 定义方式（以C语言为例）：
  数据类型 数组名[数组长度];

• 随机访问：数组支持随机存取，任一元素 aᵢ 的存储地址可通过公式计算：
  LOC(aᵢ) = LOC(a₁) + (i - 1) × k
  其中 k 为每个元素占用的存储单元数。

• 常见操作：

  • 删除尾部元素：只需将元素计数减1。

  • 删除第 i 个位置元素：需将后续元素依次左移，并更新计数。

• Python 中的数组：Python 使用列表（list）表示数组，元素类型可以不同，支持一维和多维（如嵌套列表）。

  题解：

  定义查找区间： 初始化双指针 i , j 分别指向数组首、尾元素，代表查找区间为闭区间 [i,j] ；

  循环二分，缩窄查找区间：

  使用向下取整除法，计算区间 [i,j] 的中点 m ；

  若 nums[m]<target ，根据数组有序性，易得 target 一定不在闭区间 [i,m] 中，因此执行 i=m+1 ，即将查找区间缩窄至 [m+1,j] ；

  若 nums[m]>target ， 根据数组有序性，易得 target 一定不在闭区间 [m,j] 中，因此执行 j=m−1 ，即将查找区间缩窄至 [i,m−1] ；

  若 nums[m]=target ，说明找到 target ，返回索引 m 即可；

  不满足 i≤j 时跳出循环，此时代表无法在数组中找到 target ，因此返回 −1 ；

  需注意，若数组长度取值范围较大，计算中点操作 m= 2i+j中的 i+j 可能超出 int 类型的取值范围，从而导致计算错误。此时，需使用 m=i+ 2j−i 计算中点，避免此问题。

• 左闭右闭

• left 和 right 都包含在查找范围内

• 初始：left = 0，right = len(nums) - 1

• 循环条件：left <= right（因为 left 和 right 都有效，相等时区间里还有一个元素）

• left 包含在查找范围内，right 不包含

• 左闭右开

• left 包含在查找范围内，right 不包含

• 初始：left = 0，right = len(nums)（right 指向数组末尾的下一个位置，不参与查找）

• 循环条件：left < right（因为 right 本身不在范围内，相等时区间已经空了）

• 更新 right：right = mid（因为右开，mid 不包含，直接设为 mid 即可）

• 更新 left：left = mid + 1（和左闭右闭一样）