C++算法（查找算法）

1. 二分查找（Binary Search）

时间复杂度：O(log n)

空间复杂度：O(1)

前提条件：数组必须有序

原理：每次将搜索区间减半

// 迭代版本
int binarySearch(vector<int>& arr, int target) {
    int left = 0, 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;  // 未找到
}

// 递归版本
int binarySearchRecursive(vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

// 使用示例
int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);
    cout << "元素 " << target << " 在索引: " << result << endl;
}

2. 查找数组中的最大值和最小值

时间复杂度：O(n)

空间复杂度：O(1)

// 方法1：遍历查找
pair<int, int> findMinMax(vector<int>& arr) {
    if (arr.empty()) {
        throw runtime_error("数组为空");
    }
    
    int minVal = arr[0];
    int maxVal = arr[0];
    
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < minVal) {
            minVal = arr[i];
        }
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    
    return {minVal, maxVal};
}

// 方法2：使用 STL
pair<int, int> findMinMaxSTL(vector<int>& arr) {
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    return {minVal, maxVal};
}

// 方法3：分治法（更高效，比较次数更少）
pair<int, int> findMinMaxDivide(vector<int>& arr, int left, int right) {
    // 只有一个元素
    if (left == right) {
        return {arr[left], arr[left]};
    }
    
    // 只有两个元素
    if (right == left + 1) {
        if (arr[left] < arr[right]) {
            return {arr[left], arr[right]};
        } else {
            return {arr[right], arr[left]};
        }
    }
    
    // 分治
    int mid = left + (right - left) / 2;
    auto leftResult = findMinMaxDivide(arr, left, mid);
    auto rightResult = findMinMaxDivide(arr, mid + 1, right);
    
    int minVal = min(leftResult.first, rightResult.first);
    int maxVal = max(leftResult.second, rightResult.second);
    
    return {minVal, maxVal};
}

// 使用示例
int main() {
    vector<int> arr = {3, 5, 1, 9, 2, 8, 4};
    auto result = findMinMax(arr);
    cout << "最小值: " << result.first << ", 最大值: " << result.second << endl;
}

3. 查找数组中的重复元素

多种方法实现

// 方法1：使用哈希表（unordered_set）
// 时间复杂度：O(n)，空间复杂度：O(n)
vector<int> findDuplicates1(vector<int>& arr) {
    unordered_set<int> seen;
    unordered_set<int> duplicates;
    
    for (int num : arr) {
        if (seen.count(num)) {
            duplicates.insert(num);
        } else {
            seen.insert(num);
        }
    }
    
    return vector<int>(duplicates.begin(), duplicates.end());
}

// 方法2：使用哈希表统计频率
// 时间复杂度：O(n)，空间复杂度：O(n)
vector<int> findDuplicates2(vector<int>& arr) {
    unordered_map<int, int> freq;
    vector<int> result;
    
    for (int num : arr) {
        freq[num]++;
    }
    
    for (auto& pair : freq) {
        if (pair.second > 1) {
            result.push_back(pair.first);
        }
    }
    
    return result;
}

// 方法3：排序后查找
// 时间复杂度：O(n log n)，空间复杂度：O(1)
vector<int> findDuplicates3(vector<int>& arr) {
    vector<int> result;
    if (arr.empty()) return result;
    
    sort(arr.begin(), arr.end());
    
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] == arr[i - 1] && (result.empty() || result.back() != arr[i])) {
            result.push_back(arr[i]);
        }
    }
    
    return result;
}

// 方法4：如果数组元素范围是 [1, n]，可以使用索引标记法
// 时间复杂度：O(n)，空间复杂度：O(1)
vector<int> findDuplicates4(vector<int>& arr) {
    vector<int> result;
    
    for (int i = 0; i < arr.size(); i++) {
        int index = abs(arr[i]) - 1;
        if (arr[index] < 0) {
            result.push_back(abs(arr[i]));
        } else {
            arr[index] = -arr[index];
        }
    }
    
    // 恢复数组
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = abs(arr[i]);
    }
    
    return result;
}

// 使用示例
int main() {
    vector<int> arr = {4, 3, 2, 7, 8, 2, 3, 1};
    auto result = findDuplicates1(arr);
    cout << "重复元素: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
}

4. 查找数组中缺失的最小正整数

时间复杂度：O(n)

空间复杂度：O(1)

// 方法1：使用索引标记法（最优解）
int findMissingPositive(vector<int>& arr) {
    int n = arr.size();
    
    // 第一步：将所有负数、0 和大于 n 的数替换为 n+1
    for (int i = 0; i < n; i++) {
        if (arr[i] <= 0 || arr[i] > n) {
            arr[i] = n + 1;
        }
    }
    
    // 第二步：使用索引标记法，将对应位置的数变为负数
    for (int i = 0; i < n; i++) {
        int num = abs(arr[i]);
        if (num <= n) {
            arr[num - 1] = -abs(arr[num - 1]);
        }
    }
    
    // 第三步：找到第一个正数的位置
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            return i + 1;
        }
    }
    
    return n + 1;
}

// 方法2：使用哈希集合
// 时间复杂度：O(n)，空间复杂度：O(n)
int findMissingPositive2(vector<int>& arr) {
    unordered_set<int> numSet(arr.begin(), arr.end());
    
    int i = 1;
    while (numSet.cou