当前位置：首页 > news >正文

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

news 2026/5/27 7:31:56

在算法学习中，二分查找、全排列、子集生成是非常基础且重要的内容。本文将结合 C++ 代码，详细讲解这三种经典算法的实现思路与核心逻辑，帮助大家理解算法的底层原理和代码落地方式。

一、二分查找（Binary Search）

二分查找是一种高效的查找算法，适用于有序数组的查找场景，时间复杂度为 O (logn)，相比顺序查找的 O (n)，效率提升显著。

1. 核心思路

二分查找的核心是 “折半思想”：

定义左右指针left和right，分别指向数组首尾；
计算中间位置mid，比较目标值与ar[mid]的大小：
- 若目标值小于ar[mid]，则目标值在左半区间，调整右指针；
- 若目标值大于ar[mid]，则目标值在右半区间，调整左指针；
- 若相等，则找到目标值（本文额外处理了 “找第一个匹配值” 的场景）；
重复上述过程，直到找到目标值或指针越界。

2. 代码实现（含 “找第一个匹配值”）

#include<stdio.h> #include<iostream> 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) { // 避免(left+right)/2的溢出问题，等价于(left+right)/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避免了(left+right)/2可能出现的整数溢出问题。

二、全排列（Permutation）

全排列是指从 n 个不同元素中取出 m 个元素，按照一定的顺序排列起来，当 m=n 时即为全排列。本文实现的是无重复元素的全排列，核心思路是回溯法。

1. 核心思路

定义递归函数Perm(ar, k, m)，表示 “处理第 k 个位置，数组末尾为 m”；
当k == m时，说明已处理完所有位置，输出当前排列；
否则，遍历从 k 到 m 的元素，将每个元素与第 k 个位置交换，递归处理下一个位置，递归返回后再交换回来（回溯），恢复原数组。

2. 代码实现

#include<stdio.h> #include<iostream> 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. 核心思路

定义辅助数组br，br[i]=1表示选择ar[i]，br[i]=0表示不选；
递归函数func(ar, br, k, n)表示 “处理第 k 个元素，数组长度为 n”；
当k >= n时，遍历辅助数组，输出选中的元素（未选中的用#占位）；
否则，先标记第 k 个元素为 “选中”（br[k]=1），递归处理下一个元素；再标记为 “不选中”（br[k]=0），递归处理下一个元素。

2. 代码实现

#include<stdio.h> #include<iostream> 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; }