Problem.png
输入乱序的一些数，先从小到大排序后再查询某个数是否在这个数列中，在则输出其位置。
读入数据后先快排再二分查找，但是相同的数要求输出第一个位置，因此在二分查找的函数中，查到对应的值后还要继续往前找直到找到第一个位置。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10005;
int num[maxn] = { 0 };
// 二分查找
int found(int q, int a[], int N) {
int high = N - 1, low = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == q) {
// 找到后再向前找到第一个出现的位置
for (int i = mid; ; i--) {
if (a[i] != q) {
return i + 2;
}
}
}
else if (a[mid] > q) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
int main() {
int N, Q;
int C = 1;
while (cin >> N >> Q && N) {
for (int i = 0; i < N; i++) {
cin >> num[i];
}
sort(num, num + N);
int q;
cout << "CASE# " << C << ":" << endl;
C++;
for (int i = 0; i < Q; i++) {
cin >> q;
int pos = found(q, num, N);
if (pos == -1) {
cout << q << " not found" << endl;
}
else {
cout << q << " found at " << pos << endl;
}
}
}
}
