d732: 二分搜尋法

2019-09-03

內容

給你一個嚴格遞增的數列 A1,A2,A3…..An(1<=n<=100000),

&下面有幾個問題的詢問數 k(1<=K<=100000),

以及 k 個詢問的整數 x,求數列中是否存在一個 Ai(1<=i<=n)的值與 X 相等?

輸入

第一行包含兩個整數 n,k 分別表示數列長度以及詢問數,

第二行包含 n 個整數第 i(1<=i<=n)個整數依序為數列中 Ai 的值,

第三行包含 k 個詢問的整數 x.

5 5
1 3 4 7 9
3 1 9 7 -2

輸出

對於每個詢問整數 x 對應一行輸出:

輸出 i 的值

其中 1<=i<=n 且 Ai=x

若沒有這樣的 i 值請輸出 0 代替.

2
1
5
4
0

解題思路

實作二分搜索法，輸入輸出很大做 IO 優化可以壓不少時間。

完整程式碼

AC (16ms, 1.5MB)

#include <stdio.h>
#include <stdlib.h>
#define BUFSIZ 1048576
#define MAX 100010

int list[MAX];

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readInt(int* dst)
{
    register char ch;
    while ((ch = readChar()) < '-')
        if (ch == EOF) return 0;
    if (ch == '-')
    {
        *dst = readChar() ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
        *dst = ~*dst + 1;
    }
    else
    {
        *dst = ch ^ '0';
        while ((ch = readChar()) >= '0')
            * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    }
    return 1;
}

inline void putUInt(register unsigned int src, const char suffix)
{
    register unsigned int div;
    char buffer[12], * st = buffer + 10;
    *st = suffix, * (st + 1) = 0;
    do
    {
        *(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
    } while (src = div);
    fputs(st, stdout);
}

int cmp(const void* lhs, const void* rhs)
{
    return *(int*)lhs - *(int*)rhs;
}

int main()
{
    int n, m, key, * idx;
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < n; i++)
        readInt(&list[i]);
    while (m--)
    {
        readInt(&key);
        if (idx = (int*)bsearch(&key, list, n, sizeof(int), cmp))
           putUInt(idx - list + 1, '\n');
        else
            puts("0");
    }
    return 0;
}