hihoCoder 1128-二分·二分查找 #1128 : 二分·二分查找 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Nettle最近在玩《艦これ》，因此Nettle收集了很多很多的船(这里我们假设Nettle氪了很多金，开了无数个船位)。去除掉重复的船之后，还剩下N(1≤N≤1,000,000)种不同的船。每一艘船有一个稀有值，任意两艘船的稀有值都不相同，稀有值越小的船越稀有，价值也就越高。 Nettle现在通过大建又造出了一艘船，他想知道这艘船是不是重复的。如果是重复的，那么这艘船在Nettle所有的船里面稀有值排多少位。 问题一 Nettle已经先把自己所有船按照稀有值从小到大排列好了(a[1..N])，我们要做的是看看新得到的船(假设稀有值为K)是否在这个序列中，且有对应的a[i]=K时，i为多少？ 提示一：有序数组的二分查找 问题二 因为Nettle的船太多了，他不愿意去给所有船按照稀有值排序，而是直接告诉了我们每一艘船的稀有值。在这种情况下我们该如何解决这个问题呢？ 提示二：非有序数组的二分查找 输入 第1行：2个整数N,K。N表示数组长度，K表示需要查找的数； 第2行：N个整数，表示a[1..N]，保证不会出现重复的数，1≤a[i]≤2,000,000,000。 输出 第1行：一个整数t，表示K在数组中是第t小的数，若K不在数组中，输出-1。 样例输入 10 5180 2970 663 5480 4192 4949 1 1387 4428 5180 2761 样例输出 9
给出一串数字，问某个数字K在该序列中是第几小的。 最简单的解法，遍历一遍数组，找出比K小的数的个数n，则K是第n+1小的数。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> a; int n, k; int main() { scanf("%d %d", &n, &k); a.resize(n); bool is_exist = false; int ans = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] == k) is_exist = true; if (a[i] < k) ans++; } if (!is_exist) printf("-1\n"); else printf("%d\n", ans + 1); return 0; } [/cpp] 本代码提交AC，用时58MS，内存3MB。 但是题意显然不是用这种方法，为了配合下一题的求第k小数，提示使用快排的中间步骤，依次将序列划分成比某个数大和比某个数小的两部分，再在其中某个子序列中递归求解。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> a; int n, k; int GetOrder(int p, int q) { int m = a[p]; int i = p, j = q; while (i < j) { while (i < j&&a[j] > m) j–; a[i] = a[j]; while (i < j&&a[i] < m) i++; a[j] = a[i]; } if (k == m) return i; else if (k < m) return GetOrder(p, i – 1); else return GetOrder(i + 1, q); } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); a.resize(n); bool is_exist = false; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] == k) is_exist = true; } if (!is_exist) printf("-1\n"); else printf("%d\n", GetOrder(0, n – 1) + 1); return 0; } [/cpp] 本代码提交AC，用时57MS，内存3MB。]]>