经典算法实现：二分查找、全排列与子集生成

在算法学习中二分查找、全排列、子集生成是非常基础且重要的内容。本文将结合 C 代码详细讲解这三种经典算法的实现思路与核心逻辑帮助大家理解算法的底层原理和代码落地方式。一、二分查找Binary Search二分查找是一种高效的查找算法适用于有序数组的查找场景时间复杂度为 O (logn)相比顺序查找的 O (n)效率提升显著。1. 核心思路二分查找的核心是 “折半思想”定义左右指针left和right分别指向数组首尾计算中间位置mid比较目标值与ar[mid]的大小若目标值小于ar[mid]则目标值在左半区间调整右指针若目标值大于ar[mid]则目标值在右半区间调整左指针若相等则找到目标值本文额外处理了 “找第一个匹配值” 的场景重复上述过程直到找到目标值或指针越界。2. 代码实现含 “找第一个匹配值”#includestdio.h #includeiostream using namespace std; // 二分查找找到第一个匹配val的位置 int FindValue(const int* ar, int n, int val) { if (nullptr ar || n 1) return -1; // 边界校验 int left 0, right n - 1; int pos -1; while (left right) { // 避免(leftright)/2的溢出问题等价于(leftright)/2 int mid (right - left 1) / 2 left; if (val ar[mid]) { right mid - 1; // 目标在左半区间 } else if (val ar[mid]) { left mid 1; // 目标在右半区间 } else { // 找到匹配值后继续向左找第一个匹配项 if (mid left ar[mid - 1] val) { right mid - 1; } else { pos mid; break; } } } return pos; } // 递归版二分查找基础版不找第一个匹配值 int BinFindValue(const int* ar, int left, int right, int val) { int pos -1; if (left right) { int mid (right - left 1) / 2 left; if (val ar[mid]) { pos BinFindValue(ar, left, mid - 1, val); } else if (val ar[mid]) { pos BinFindValue(ar, mid 1, right, val); } else { pos mid; } } return pos; } // 递归二分查找入口 int BinaryFindValue(const int* ar, int n, int val) { if (nullptr ar || n 1) return -1; return BinFindValue(ar, 0, n - 1, val); } // 测试二分查找 int main() { int ar[] { 12,23,34,45,56,67,78,89,90,100,110 }; int n sizeof(ar) / sizeof(ar[0]); int val; while (cin val, val ! -1) { int pos FindValue(ar, n, val); printf(目标值%d的位置%d\n, val, pos); } return 0; }3. 关键说明非递归版FindValue处理了 “数组中有重复元素找第一个匹配值” 的场景这是二分查找的常见变种递归版BinaryFindValue更简洁但递归深度过大会导致栈溢出实际场景中更推荐非递归版mid的计算方式(right - left 1) / 2 left避免了(leftright)/2可能出现的整数溢出问题。二、全排列Permutation全排列是指从 n 个不同元素中取出 m 个元素按照一定的顺序排列起来当 mn 时即为全排列。本文实现的是无重复元素的全排列核心思路是回溯法。1. 核心思路定义递归函数Perm(ar, k, m)表示 “处理第 k 个位置数组末尾为 m”当k m时说明已处理完所有位置输出当前排列否则遍历从 k 到 m 的元素将每个元素与第 k 个位置交换递归处理下一个位置递归返回后再交换回来回溯恢复原数组。2. 代码实现#includestdio.h #includeiostream using namespace std; // 全排列核心函数 void Perm(int* ar, int k, int m) { if (k m) // 递归终止已处理完所有位置 { for (int i 0; i m; i) { printf(%3d, ar[i]); } printf(\n); } else { for (int j k; j m; j) { swap(ar[k], ar[j]); // 交换当前位置与后续位置的元素 Perm(ar, k 1, m); // 递归处理下一个位置 swap(ar[k], ar[j]); // 回溯恢复原数组 } } } // 测试全排列 int main() { int ar[] { 1,2,3 }; int n sizeof(ar) / sizeof(ar[0]); Perm(ar, 0, n - 1); return 0; }3. 关键说明回溯法是全排列的核心通过 “交换 - 递归 - 回溯” 的方式遍历所有可能的排列该代码适用于无重复元素的数组若数组有重复元素需额外增加 “去重” 逻辑如跳过相同元素的交换。三、子集生成Subset Generation子集生成是找出一个集合的所有子集本文通过 “0-1 标记法” 结合回溯实现核心思想是 “每个元素有选或不选两种状态”。1. 核心思路定义辅助数组brbr[i]1表示选择ar[i]br[i]0表示不选递归函数func(ar, br, k, n)表示 “处理第 k 个元素数组长度为 n”当k n时遍历辅助数组输出选中的元素未选中的用#占位否则先标记第 k 个元素为 “选中”br[k]1递归处理下一个元素再标记为 “不选中”br[k]0递归处理下一个元素。2. 代码实现#includestdio.h #includeiostream using namespace std; // 子集生成核心函数 void func(const int* ar, int* br, int k, int n) { if (k n) // 递归终止处理完所有元素 { for (int i 0; i n; i) { if (br[i] 1) { printf(%5d, ar[i]); } else { printf(%5c, #); } } printf(\n); } else { br[k] 1; func(ar, br, k 1, n); // 选择第k个元素递归 br[k] 0; func(ar, br, k 1, n); // 不选择第k个元素递归 } } // 测试子集生成 int main() { int ar[] { 1,2,3 }; int br[] { 0,0,0 }; // 辅助数组标记元素是否被选中 func(ar, br, 0, 3); return 0; }3. 关键说明该方法的时间复杂度为 O (2^n)因为每个元素有两种状态n 个元素的子集总数为 2^n辅助数组br的作用是记录元素的选择状态是回溯法中 “状态记录” 的典型应用输出时用#占位未选中的元素便于直观看到所有子集的构成空集对应全#。四、总结本文实现了三种经典算法二分查找高效查找有序数组重点掌握折半思想和边界处理尤其是重复元素场景的变种全排列回溯法的经典应用核心是 “交换 - 递归 - 回溯”需理解回溯的本质是恢复现场子集生成通过 0-1 标记法遍历所有元素的选择状态是回溯法解决组合问题的典型思路。这些算法是算法学习的基础掌握其核心思想后可拓展到更复杂的场景如带重复元素的全排列、子集去重、二分查找的变种问题等。建议大家手动敲写代码调试理解每一步的执行逻辑加深对算法的理解。