狗熊岭美人松查找问题的 C++ 实现

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <cstdio> // 二分查找函数，用于查找高度为 target 的美人松是否存在 bool binarySearch(long long arr[], int n, long long target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return true; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return false; } int main() { int n, m; // 使用 scanf 读取 n 和 m scanf("%d %d", &n, &m); long long trees[1000000]; // 读取 n 棵美人松的高度 for (int i = 0; i < n; i++) { scanf("%lld", &trees[i]); } for (int i = 0; i < m; i++) { long long k; // 读取每次询问的高度 k scanf("%lld", &k); // 调用二分查找函数判断高度为 k 的美人松是否存在 if (binarySearch(trees, n, k)) { printf("1"); } else { printf("0"); } if (i < m - 1) { printf(" "); } } printf("\n"); return 0; } ``` ### 代码解释： 1. **二分查找函数 `binarySearch`**：该函数接受一个已排序的数组 `arr`、数组长度 `n` 和目标值 `target` 作为参数。通过不断缩小查找范围，判断目标值是否存在于数组中。如果存在，返回 `true`；否则返回 `false`。 2. **主函数 `main`**： - 首先使用 `scanf` 读取 `n` 和 `m`，分别表示美人松的数量和询问的次数。 - 接着读取 `n` 棵美人松的高度，并存储在数组 `trees` 中。 - 然后进行 `m` 次询问，每次读取一个高度 `k`，调用 `binarySearch` 函数判断高度为 `k` 的美人松是否存在。如果存在，输出 `1`；否则输出 `0`。 ### 复杂度分析： - **时间复杂度**：二分查找的时间复杂度为 $O(log n)$，对于 $m$ 次询问，总的时间复杂度为 $O(m log n)$。 - **空间复杂度**：只使用了一个长度为 $n$ 的数组来存储美人松的高度，因此空间复杂度为 $O(n)$。 ######[AI问答 | 683点数解答 | 2026-02-24 19:56:05]