求c++代码 二分查找 时间限制:1秒 内存限制:128M 题目描述 给出有n 个元素的由小到大的序列,请你编程找出某元素第一次出现的位置。(n<=10^6) 输入描述 第一行:一个整数,表示由小到大序列元素个数; 接下来下面 n 行,每行一个整数; 最后一行一个整数 x,表示待查找的元素。 输出描述 如果x在序列中,则输出x第一次出现的位置,否则输出-1。 样例 输入 5 3 5 6 6 7 6 输出 3
时间: 2024-01-17 14:03:00 浏览: 55
好的,下面是 C++ 的代码实现:
```c++
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int x) {
int left = 0, right = n - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] == x) {
while (mid > 0 && arr[mid - 1] == x) {
mid--;
}
return mid;
}
else if (arr[mid] > x) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
int main() {
int n, x;
cin >> n;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cin >> x;
cout << binarySearch(arr, n, x) << endl;
return 0;
}
```
代码中的 `binarySearch` 函数就是实现二分查找的核心代码。在找到要查找的元素时,使用了一个 `while` 循环来找到该元素第一次出现的位置。
具体来说,当找到元素时,先将 mid 更新为该元素的位置,然后在该位置的左边继续查找是否还有相同的元素,如果有就将 mid 继续左移,直到 mid 左边不存在相同的元素为止,最后返回 mid。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)