数据结构与算法再探（七）查找-排序

查找

一、二分查找

二分查找是一种高效的查找算法，适用于在已排序的数组或列表中查找特定元素。它通过将搜索范围逐步减半来快速定位目标元素。理解二分查找的“不变量”和选择左开右闭区间的方式是掌握这个算法的关键。

二分查找关键点

不变量

在二分查找中，不变量是指在每一步迭代中保持不变的条件。对于二分查找来说，不变量通常是：目标值在当前搜索范围内：在每次迭代中目标值始终位于 left 和 right 指针之间。如在查找一个值 target并且当前的搜索范围是 arr[left]- arr[right]，那么我们可以保证如果 arr[left]≤target≤arr[right]，则 target 一定在这个范围内。

区间定义

二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，二分查找中的左闭右开和左闭右闭的本质区别主要体现在搜索范围的定义和边界处理上。这种选择会影响算法的实现细节、边界条件的处理以及最终的查找结果。

二分查找实现

1）左闭右闭区间 [left, right]

定义：left 和 right 都是闭合的，表示搜索范围包括 left 和 right。当 left 等于 right 时，搜索范围仍然包含 right。在计算中间值时，使用 mid = left + (right - left) / 2。但是：这种都是闭区间可能会导致重复元素的处理变得复杂，特别是在查找第一个或最后一个出现的元素时。

int binarySearchClosed(const std::vector<int>& arr, int target) {int left = 0;int right = arr.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标值} else if (arr[mid] < target) {left = mid + 1; // 在右半部分继续查找} else {right = mid - 1; // 在左半部分继续查找}}return -1; // 未找到目标值
}

2）左闭右开区间 [left, right)

left 是闭合的，right 是开合的，表示搜索范围包括 left，但不包括 right。当 left 等于 right 时，搜索范围不包含 right，因此 right 的值是 arr.size()。并且在更新 right 时使用 right = mid。优点：避免了中间元素重复的情况，特别适合查找插入位置。逻辑上更容易处理边界条件，特别是在处理空数组或查找插入位置时。但是没有左闭右闭直观。

int binarySearchOpen(const std::vector<int>& arr, int target) {int left = 0;int right = arr.size(); // 注意这里是 arr.size()while (left < right) { // 注意这里是 left < rightint mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标值} else if (arr[mid] < target) {left = mid + 1; // 在右半部分继续查找} else {right = mid; // 在左半部分继续查找}}return -1; // 未找到目标值
}

二分区间查找

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution {// lower_bound 返回最小的满足 nums[i] >= target的下标 i// 如果数组为空，或者所有数都 <target，则返回nums.size()int lower_bound(vector<int>& nums, int target) {int left = 0, right = (int) nums.size() - 1; // 闭区间while (left <= right) {// 循环不变量：nums[left-1] < target   nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1; } else {left = mid + 1; }}// 循环结束后 left = right+1// 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target// 所以 left 就是第一个 >= target 的元素下标return left;}
public:vector<int> searchRange(vector<int>& nums, int target) {int start = lower_bound(nums, target);if (start == nums.size() || nums[start] != target) {return {-1, -1}; // nums 中没有 target}// 如果 start 存在，那么 end 必定存在int end = lower_bound(nums, target + 1) - 1;return {start, end};}
};

 

二、深度搜索

沿分支尽可能深入，到达叶子节点后回溯，继续探索其他分支。

113. 路径总和 II - 力扣（LeetCode）

class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:def dfs(node, path, current_sum):if not node:returncurrent_sum += node.valpath.append(node.val)if not node.left and not node.right and current_sum == targetSum:result.append(list(path))dfs(node.left, path, current_sum)dfs(node.right, path, current_sum)path.pop()  # 回溯result = []dfs(root, [], 0)return result

三、广度搜索

按层级逐层遍历，先处理离根节点最近的节点，可以使用队列（FIFO）存储待访问节点。

102. 二叉树的层序遍历 - 力扣（LeetCode）

BFS层次遍历

class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if root is None:return []ans=[]q=deque([root])while q:vals=[]for _ in range(len(q)):node=q.popleft()vals.append(node.val)if node.left: q.append(node.left)if node.right:q.append(node.right)ans.append(vals)return ans

200. 岛屿数量 - 力扣（LeetCode） 

BFS

def numIslands(grid):if not grid:return 0rows, cols = len(grid), len(grid[0])count = 0from collections import dequefor i in range(rows):for j in range(cols):if grid[i][j] == '1':queue = deque([(i, j)])grid[i][j] = '0'  # 标记为已访问while queue:x, y = queue.popleft()for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:nx, ny = x + dx, y + dyif 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':queue.append((nx, ny))grid[nx][ny] = '0'count += 1return count

DFS

def numIslands(grid):def dfs(x, y):if 0 <= x < rows and 0 <= y < cols and grid[x][y] == '1':grid[x][y] = '0'dfs(x+1, y)dfs(x-1, y)dfs(x, y+1)dfs(x, y-1)rows = len(grid)if rows == 0:return 0cols = len(grid[0])count = 0for i in range(rows):for j in range(cols):if grid[i][j] == '1':dfs(i, j)count += 1return count

排序

排序算法总结-CSDN博客

数组中第K大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

要在时间复杂度为O(n) 的情况下找到数组中第k个最大的元素，可以使用快速选择（Quickselect）算法。这个算法的思想与快速排序相似，但它只关注找到第k 个最大的元素，而不是对整个数组进行排序。（排序后return nums[nums.size() - k];  O(nlogn)）

选择基准元素：从数组中随机选择一个基准元素。（快排一趟确定一个元素的位置）
分区操作：将数组分为两部分，左侧是小于基准的元素，右侧是大于基准的元素。
判断基准位置：如果基准元素的位置正好是n−k（因为我们需要找到第k 个最大的元素），那么这个元素就是我们要找的元素。如果基准元素的位置大于n−k，则第k 个最大的元素在左侧部分。
如果基准元素的位置小于n−k，则第k 个最大的元素在右侧部分。

class Solution {
public:int quickselect(vector<int> &nums, int l, int r, int k) {if (l == r)return nums[k];int partition = nums[l], i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < partition);do j--; while (nums[j] > partition);if (i < j)swap(nums[i], nums[j]);}if (k <= j)return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}int findKthLargest(vector<int> &nums, int k) {int n = nums.size();return quickselect(nums, 0, n - 1, n - k);}
};