二分查找——UVa 10706 - Number Sequence

思路：

要得到給定位置的數字，隻需要知道該位置處在的序列Sk和距離Sk首位的偏移量即可。

設seqLen[k]表示：S1S2…Sk的總長度，對于給定的i，用二分查找确定所在的Sk, i-Sk-1就是偏移量。

/*
Sk的長度：
k的範圍
[1  , 9  ]: k
[10 , 99 ]: 9 + (k-9)*2
[100, 999]: 9 + 90*2 + (k-99)*3
...
*/

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

#define MAXN 31270
#define MAXLEN 146000

unsigned int seqLen[MAXN];

void InitSequenceLength(void)
{
	seqLen[0] = 0;
	unsigned int delta = 1, c = 10, sum = 0;

	int i;
	for (i = 1; seqLen[i-1] <= 2147483647; i++)
	{
		//當i為10、100、1000...時，delta需要加1
		if (i == c)
		{
			delta++;
			c *= 10;
		}
		sum += delta;
		seqLen[i] = seqLen[i-1] + sum;
	}
}

int BSearch(int low, int high, unsigned int targ)
{
	while (low <= high)
	{
		int mid = (low + high) / 2;

		if (targ == seqLen[mid])
		{
			return seqLen[mid-1];
		}
		else if (targ < seqLen[mid])
		{
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
	return seqLen[high];
}

int main(void)
{
	InitSequenceLength();
	string maxSeq;
	maxSeq.reserve(MAXLEN+10);
	int i;
	for (i = 1; maxSeq.length() < MAXLEN; i++)
	{
		char temp[10];
		sprintf(temp, "%d", i);
		maxSeq += temp;
	}

	int ncases;
	scanf("%d", &ncases);

	while (ncases-- != 0)
	{
		unsigned int p;
		scanf("%d", &p);
		int i = BSearch(1, 31268, p);
		printf("%c\n", maxSeq[p-i-1]);
	}
	return 0;
}