大家好，我是讯享网，很高兴认识大家。这里提供最前沿的Ai技术和互联网信息。



功能

在有序数组中查找目标值，找到返回下标，找不到返回 -1。

亮点

• 防止 mid 计算溢出
• 标准循环写法
• 严格 C++ 规范

 #include 
  
    
    
      #include 
     
       using namespace std; // 二分查找：普通版 // arr：有序数组 // n：数组长度 // val：要查找的值 // 返回值：找到返回下标，失败返回 -1 int FindValue(const int* arr, int n, int val) else if (arr[mid] < val) { // 目标值更大，去右区间 left = mid + 1; } else { // 找到目标值 pos = mid; break; } } return pos; } // 递归二分查找核心函数 int BinFindValue(const int* arr, int left, int right, int val) else if (val > arr[mid]) { // 递归右区间 return BinFindValue(arr, mid + 1, right, val); } else { // 找到值 pos = mid; } } return pos; } // 递归二分查找对外接口 int BinaryFindValue(const int* arr, int n, int val) // 测试主函数 int main() { int arr[] = { 12,23,34,45,56,67,78,89,90,100,110 }; int n = sizeof(arr) / sizeof(arr[0]); int val; // 循环输入查找，输入 -1 退出 while (cin >> val, val != -1) { // int pos = FindValue(arr, n, val); int pos = BinaryFindValue(arr, n, val);//递归 cout << "pos = " << pos << endl; } return 0; } 
      
    

---

功能

数组存在重复数字时，返回第一次出现的位置（最左下标）。

思路

找到相等值不退出，继续向左搜索，直到找到最左端。

 #include 
   
    
     
       #include 
      
        using namespace std; // 二分查找：重复数返回【最左下标】 int FindValue(const int* arr, int n, int val) else if (val > arr[mid]) { left = mid + 1; } else else { // 找到最左位置 pos = mid; break; } } } return pos; } // 测试主函数 int main() { // 含重复数据的数组 int arr[] = { 12,12,12,12,12,23,23,23,34,45,56,67,78,89,90 }; int n = sizeof(arr) / sizeof(arr[0]); int val; while (cin >> val, val != -1) { int pos = FindValue(arr, n, val); cout << "pos = " << pos << endl; } return 0; } 
       
     

---

功能

输出数组的所有排列组合，例如 1,2,3 输出 6 种排列。

思想

交换 + 递归 + 回溯（交换回去）

 #include 
    
    
      
        #include 
       
         #include 
        
          using namespace std; // 递归全排列 // arr：数组 // k：当前固定的位置 // m：最后一个元素下标 void Perm(int* arr, int k, int m) cout << endl; } else { // 枚举 k 位置可以放的所有数字 for (int j = k; j <= m; j++) { // 交换：将 arr[j] 固定到 k 位置 swap(arr[j], arr[k]); // 递归处理下一个位置 Perm(arr, k + 1, m); // 回溯：恢复原状 swap(arr[j], arr[k]); } } } // 测试主函数 int main() { int arr[] = { 1,2,3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "全排列结果：" << endl; Perm(arr, 0, n - 1); return 0; } 
         
        
      

---

功能

输出数组的所有子集（共 2ⁿ 个）。

• 1 表示选择该元素
• 0 表示不选择该元素
• 用 # 表示不输出

 #include 
     
    
       
         #include 
        
          #include 
         
           using namespace std; // 递归子集树：枚举所有子集 // arr：原数组 // br：标记数组 1=选 0=不选 // k：当前处理第 k 个元素 // n：数组总长度 void func(const int* arr, int* br, int k, int n) else } cout << endl; } else { // 左分支：选择第 k 个元素 br[k] = 1; func(arr, br, k + 1, n); // 右分支：不选第 k 个元素 br[k] = 0; func(arr, br, k + 1, n); } } // 测试主函数 int main() { int arr[] = { 1,2,3 }; int br[] = { 0,0,0 }; // 标记数组 cout << "所有子集：" << endl; func(arr, br, 0, 3); return 0; } 
          
         
       

---

1. 二分查找

• 时间复杂度：O(logn)

• 必须有序数组

• mid 防溢出：mid = (right - left + 1) / 2 + left

2. 重复数最左下标

• 找到相等不退出，继续向左搜

• 面试高频

3. 全排列

• 回溯思想

• 交换 + 递归 + 还原 • 复杂度 O(n!)

4. 子集树

• 每个元素：选 / 不选

• 共 2ⁿ 个子集 • 复杂度 O(2ⁿ)

---