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.count(i)) {
        i++;
    }
    
    return i;
}

// 方法3：排序后查找
// 时间复杂度：O(n log n)，空间复杂度：O(1)
int findMissingPositive3(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    
    int missing = 1;
    for (int num : arr) {
        if (num == missing) {
            missing++;
        } else if (num > missing) {
            break;
        }
    }
    
    return missing;
}

// 使用示例
int main() {
    vector<int> arr = {3, 4, -1, 1};
    int result = findMissingPositive(arr);
    cout << "缺失的最小正整数: " << result << endl;  // 输出: 2
}

5. 找到数组中的两个数，使它们的和为目标值（Two Sum）

多种方法实现

// 方法1：使用哈希表（最优解）
// 时间复杂度：O(n)，空间复杂度：O(n)
vector<int> twoSum1(vector<int>& arr, int target) {
    unordered_map<int, int> numMap;  // 值 -> 索引
    
    for (int i = 0; i < arr.size(); i++) {
        int complement = target - arr[i];
        if (numMap.count(complement)) {
            return {numMap[complement], i};
        }
        numMap[arr[i]] = i;
    }
    
    return {};  // 未找到
}

// 方法2：暴力法
// 时间复杂度：O(n²)，空间复杂度：O(1)
vector<int> twoSum2(vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[i] + arr[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

// 方法3：双指针法（需要先排序）
// 时间复杂度：O(n log n)，空间复杂度：O(1)
vector<int> twoSum3(vector<int>& arr, int target) {
    vector<pair<int, int>> indexed;  // {值, 原始索引}
    for (int i = 0; i < arr.size(); i++) {
        indexed.push_back({arr[i], i});
    }
    
    sort(indexed.begin(), indexed.end());
    
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int sum = indexed[left].first + indexed[right].first;
        if (sum == target) {
            return {indexed[left].second, indexed[right].second};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return {};
}

// 使用示例
int main() {
    vector<int> arr = {2, 7, 11, 15};
    int target = 9;
    auto result = twoSum1(arr, target);
    cout << "索引: [" << result[0] << ", " << result[1] << "]" << endl;
}

6. 旋转排序数组中的最小值

时间复杂度：O(log n)

空间复杂度：O(1)

// 无重复元素版本
int findMinInRotatedArray(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // 右半部分是旋转的，最小值在左半部分
        if (arr[mid] > arr[right]) {
            left = mid + 1;
        } 
        // 左半部分是有序的，最小值在左半部分（包括mid）
        else {
            right = mid;
        }
    }
    
    return arr[left];
}

// 有重复元素版本
int findMinInRotatedArrayWithDuplicates(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] > arr[right]) {
            left = mid + 1;
        } else if (arr[mid] < arr[right]) {
            right = mid;
        } else {
            // 无法判断，缩小范围
            right--;
        }
    }
    
    return arr[left];
}

// 使用示例
int main() {
    vector<int> arr1 = {4, 5, 6, 7, 0, 1, 2};
    cout << "最小值: " << findMinInRotatedArray(arr1) << endl;  // 输出: 0
    
    vector<int> arr2 = {2, 2, 2, 0, 1};
    cout << "最小值: " << findMinInRotatedArrayWithDuplicates(arr2) << endl;  // 输出: 0
}

7. 线性查找与二分查找的差异

// 线性查找（Linear Search）
// 时间复杂度：O(n)
// 空间复杂度：O(1)
// 适用场景：无序数组
int linearSearch(vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -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;
}

// 对比测试
void compareSearchMethods() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 13;
    
    cout << "线性查找结果: " << linearSearch(arr, target) << endl;
    cout << "二分查找结果: " << binarySearch(arr, target) << endl;
}

差异对比表：

8. 找出一个排序数组中的重复元素

// 方法1：二分查找变种（找第一个和最后一个位置）
vector<int> findDuplicatesInSorted(vector<int>& arr) {
    vector<int> result;
    if (arr.empty()) return result;
    
    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;
}

// 方法2：找到所有重复元素及其出现次数
map<int, int> findDuplicatesWithCount(vector<int>& arr) {
    map<int, int> duplicates;
    
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] == arr[i - 1]) {
            duplicates[arr[i]]++;
        }
    }
    
    return duplicates;
}

// 方法3：使用二分查找找到某个元素的所有出现位置
pair<int, int> findRange(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int first = -1, last = -1;
    
    // 找第一个位置
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            first = mid;
            right = mid - 1;  // 继续向左找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // 找最后一个位置
    left = 0;
    right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            last = mid;
            left = mid + 1;  // 继续向右找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return {first, last};
}

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

9. 在旋转排序数组中查找元素

时间复杂度：O(log n)

空间复杂度：O(1)

// 无重复元素版本
int searchInRotatedArray(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;
        }
        
        // 判断哪一半是有序的
        if (arr[left] <= arr[mid]) {
            // 左半部分有序
            if (arr[left] <= target && target < arr[mid]) {
                right = mid - 1;  // 目标在左半部分
            } else {
                left = mid + 1;   // 目标在右半部分
            }
        } else {
            // 右半部分有序
            if (arr[mid] < target && target <= arr[right]) {
                left = mid + 1;   // 目标在右半部分
            } else {
                right = mid - 1;  // 目标在左半部分
            }
        }
    }
    
    return -1;  // 未找到
}

// 有重复元素版本
bool searchInRotatedArrayWithDuplicates(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 true;
        }
        
        // 无法判断哪边有序
        if (arr[left] == arr[mid] && arr[mid] == arr[right]) {
            left++;
            right--;
        } else if (arr[left] <= arr[mid]) {
            // 左半部分有序
            if (arr[left] <= target && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右半部分有序
            if (arr[mid] < target && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return false;
}

// 使用示例
int main() {
    vector<int> arr = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;
    int result = searchInRotatedArray(arr, target);
    cout << "元素 " << target << " 在索引: " << result << endl;  // 输出: 4
}