1 solutions
Information
- ID
- 190
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- # Submissions
- 547
- Accepted
- 47
- Uploaded By
简简单单读懂题后就能明白,这就是一道查找题了。
然后看一下数据量,1e6那基本就是明着告诉你暴力遍历会超时了。
根据以上两点,不难想到二分查找,而本题就是考察的二分查找的左边界与右边界,找到目标编号的左边界与右边界然后除以2就得出答案了。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int nums[maxn];
int key,n;
int left_bound() {
if (n == 0) return -1;
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == key) {
right = mid - 1 ;
} else if (nums[mid] < key) {
left = mid + 1;
} else if (nums[mid] > key) {
right = mid - 1;
}
}
if (left == n || nums[left] != key) return -1;
return left;
}
int right_bound() {
if (n == 0) return -1;
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == key) {
left = mid + 1 ;
} else if (nums[mid] < key) {
left = mid + 1;
} else if (nums[mid] > key) {
right = mid - 1;
}
}
if (left == n || nums[left - 1] != key) return -1;
return left - 1;
}
int main() {
cin >> n >> key;
for (int i = 0; i < n; i++) cin >> nums[i];
sort(nums,nums + n);
if (left_bound() == -1) {
cout << "Not Found";
return 0;
}
int ans = (left_bound() + right_bound()) / 2 + 1;
cout << ans;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.