10474 - Where is the Marble?

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;
            }
        }
    }
}