刷题小记
校赛狙击失败&蓝桥杯国赛拿了国三。反思：对于一些简单的算法的细节却不是很到位，于是回过头来重刷。
P2249【深基13.例1】查找
二分查找，手撕的时候要注意的是：
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000005;
int a[MAXN];
int b[MAXN];
int find(int front, int end, int num){
//cout << "front: " << front << "end:" << end << endl;
if(front == end || front + 1 == end) {
if(a[front] == num) return front;
if(a[end] == num) return end;
return -1;
}
int mid = (front + end) / 2;
// cout << front << end << ",";
if(a[mid] < num) {
return find( mid + 1, end, num);
}else if(a[mid] > num) return find( front, mid - 1, num);
else {
int tmp = find( front, mid - 1, num);
if(tmp == -1) return mid;
return tmp;
}
return mid;
}
int main(void) {
int n, m;
cout.sync_with_stdio(false);
cin.sync_with_stdio(false);
cin >> n >> m;
for(int i = 0; i < n; ++i) {
cin >> a[i];
}
while(m--) {
int tmp;
cin >> tmp;
int call = find(0, n - 1, tmp);
if(call != -1)cout << call+1 << " ";
else cout << call << " ";
}
}
- 纯粹的二分查找之后没办法确定当前的数是最先出现的数。
- 为了解决1的问题，在==的时候加入了一个while(--)来判定，但当全部为一个数的时候，复杂度O(n),最后一个测试点tle了。
- 为了解决2的问题，想到了在==的时候继续进行二分查找（对左区间）。如果左区间没有（返回-1)的话，就返回当前mid值，否则就返回对左区间查找的结果。
- 在第3步对find()进行判定，然后再返回的时候，用一个临时变量tmp存下来，不然就会递归2次，后3个点直接tle。
模拟手撕完了，再试试stl——lower_bound()和upper_bound()，
#include <iostream>
using namespace std;
int a[1000005];
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; ++i) cin >> a[i];
while(m--) {
int query;
cin >> query;
int* result = lower_bound(a, a+n, query);
if(*result == query) cout << result - a + 1<<" ";
else cout << -1 <<" ";
}
}
好家伙，年轻人不讲武德，用stl欺负我这个模拟撕了半个小时的人。3分钟就好了。