c++算法题：求一个数在数组中出现的位置

在C++中，查找一个数在数组中出现的位置可以使用线性搜索或二分查找。以下是使用这两种方法的实现代码。

线性搜索

线性搜索适用于无序数组，遍历数组，找到目标数的位置。

#include <iostream>
#include <vector>

// 函数：在线性搜索中查找目标数的位置
std::vector<int> find_positions(const std::vector<int>& arr, int target) {
    std::vector<int> positions;
    // 遍历数组
    for (size_t i = 0; i < arr.size(); ++i) {
        // 如果找到目标数，记录其位置
        if (arr[i] == target) {
            positions.push_back(i);
        }
    }
    return positions;
}

int main() {
    // 初始化数组
    std::vector<int> arr = {1, 3, 5, 3, 9, 3, 7};
    // 目标数
    int target = 3;
    // 查找目标数的位置
    std::vector<int> positions = find_positions(arr, target);
    
    // 输出目标数的位置
    std::cout << "Positions of " << target << " in the array: ";
    for (int pos : positions) {
        std::cout << pos << " ";
    }
    std::cout << std::endl;

    return 0;
}

二分查找

二分查找适用于有序数组。使用std::lower_bound和std::upper_bound来找到目标数的范围。

#include <iostream>
#include <vector>
#include <algorithm>

// 函数：在有序数组中使用二分查找找到目标数的位置
std::vector<int> find_positions(const std::vector<int>& arr, int target) {
    std::vector<int> positions;
    // 使用 lower_bound 找到第一个不小于 target 的位置
    auto lower = std::lower_bound(arr.begin(), arr.end(), target);
    // 使用 upper_bound 找到第一个大于 target 的位置
    auto upper = std::upper_bound(arr.begin(), arr.end(), target);

    // 遍历找到所有等于 target 的位置
    for (auto it = lower; it != upper; ++it) {
        positions.push_back(std::distance(arr.begin(), it));
    }
    return positions;
}

int main() {
    // 初始化有序数组
    std::vector<int> arr = {1, 3, 3, 3, 5, 7, 9};
    // 目标数
    int target = 3;
    // 查找目标数的位置
    std::vector<int> positions = find_positions(arr, target);
    
    // 输出目标数的位置
    std::cout << "Positions of " << target << " in the array: ";
    for (int pos : positions) {
        std::cout << pos << " ";
    }
    std::cout << std::endl;

    return 0;
}

上述代码展示了如何在C++中使用线性搜索和二分查找找到一个数在数组中的所有位置。根据数组是否有序选择适合的方法。