c++ 二分查找 时间限制:1秒 内存限制:128M 题目描述 给出有n 个元素的由小到大的序列,请你编程找出某元素第一次出现的位置。(n<=10^6) 输入描述 第一行:一个整数,表示由小到大序列元素个数; 接下来下面 n 行,每行一个整数; 最后一行一个整数 x,表示待查找的元素。 输出描述 如果x在序列中,则输出x第一次出现的位置,否则输出-1。 样例 输入 5 3 5 6 6 7 6 输出 3
时间: 2024-02-18 21:04:13 浏览: 41
好的,这是一个二分查找的问题,我可以帮您解决。以下是C++代码实现:
```c++
#include<iostream>
using namespace std;
int main(){
int n, x;
cin >> n;
int nums[n];
for(int i = 0; i < n; i++){
cin >> nums[i];
}
cin >> x;
int left = 0, right = n - 1, index = -1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == x){
index = mid;
right = mid - 1;
}
else if(nums[mid] > x){
right = mid - 1;
}
else{
left = mid + 1;
}
}
cout << index << endl;
return 0;
}
```
这里的二分查找是采用了左闭右闭的区间,使用了一个变量`index`来记录第一次出现的位置,如果当前中间元素等于x,则更新`index`的值为mid,并往左边继续查找,直到左右指针相遇。如果中间元素大于x,则在左半部分继续查找;如果中间元素小于x,则在右半部分继续查找。如果最终没找到,返回-1。
相关推荐
![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_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)
![](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)