第二学期——数组、二分查找

1. 数据结构与数组基础（概念篇）

栈、队列、树等。
· 数组（Array）：
· 特点：存储在连续内存空间，通过索引（下标）访问，时间复杂度 O(1)。
· 优缺点：查找快，但插入和删除慢（需移动大量元素），且大小通常固定（静态数组）。
· 在Java/Python中：Java的ArrayList、Python的list是动态数组，可扩容。

2. 二分查找法（LeetCode 704 经典题）

核心前提：数组必须有序（通常升序）。

算法思想：

· 定义左右指针left、right，取中间mid。
· 比较nums[mid]与target：
· 相等 → 返回mid
· target更大 → 缩小左边界 left = mid + 1
· target更小 → 缩小右边界 right = mid - 1
· 循环结束未找到 → 返回 -1

时间复杂度：O(log n)（每次排除一半数据）
空间复杂度：O(1)（迭代法）

3. 代码模板（背熟）

defsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:# 注意是 <=mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1

易错点提醒：

· 循环条件用 <= 还是 <？推荐 <=，这样区间是闭区间 [left, right]，逻辑更统一。
· 防止 left+right 溢出：可用 mid = left + (right - left) // 2（但Python整数无上限，此写法更通用）。