【問題描述】
數(shù)軸上有n個點涛酗，對于任一閉區(qū)間 [a, b]，試計算落在其內(nèi)的點數(shù)皱蹦。
【輸入】
第一行包括兩個整數(shù)：點的總數(shù)n煤杀，查詢的次數(shù)m眷蜈。
第二行包含n個數(shù)沪哺，為各個點的坐標(biāo)。
以下m行酌儒，各包含兩個整數(shù)：查詢區(qū)間的左辜妓、右邊界a和b。
【輸出】
對每次查詢，輸出落在閉區(qū)間[a, b]內(nèi)點的個數(shù)籍滴。
【輸入樣例】
5 2
1 3 7 9 11
4 6
7 12
【輸出樣例】
0
3
【限制】
0 ≤ n, m ≤ 5×105
對于次查詢的區(qū)間[a, b]酪夷，都有a ≤ b
各點的坐標(biāo)互異
各點的坐標(biāo)、查詢區(qū)間的邊界a孽惰、b晚岭，均為不超過10^7的非負(fù)整數(shù)
時間：2s，內(nèi)存：256MB
【solution】先不廢話勋功，先貼源代碼：<code><pre>
#include <stdio.h>
#include <stdlib.h> <br />
#define L 500005 <br />
int a[L]; <br />
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa) - (*pb);
} <br />
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
} <br />
int find(int begin, int end, int ac)
{
int mid, left = begin, right = end;
while (left <= right)
{
mid = left + ((right - left) >> 1);
if (a[mid] >= ac) right = mid - 1;
else left = mid + 1;
}
return left;
} <br />
int main()
{
int n, m, i;
scanf("%d %d\n", &n, &m); <br />
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
} <br />
qsort(a, n, sizeof(int), compare); <br />
for (i = 0; i < m; i++)
{
int l, r, ans, lf, rt;
scanf("%d %d", &l, &r); <br />
//make sure l <= r
if (l > r)
{
swap(l, r);
} <br />
rt = find(0, n - 1, r);
lf = find(0, n - 1, l);
ans = rt - lf;
if (a[rt] == r) ans++;
if (ans < 0) ans = 0; <br />
printf("%d\n", ans);
}
}</pre></code>
第一感覺都是這道題以前學(xué)的時候肯定做過坦报，很簡單，看到這個數(shù)據(jù)規(guī)目裥基本也就確定得用二分查找了片择。（反正看網(wǎng)上想先維護(hù)好線性數(shù)組再O(1)的查找是沒混過去的）
實際上，二分查找并沒有看起來那么簡單骚揍，尤其是具體寫起來的時候字管，有很多細(xì)節(jié)與臨界點的處理都得根據(jù)實際情況仔細(xì)斟酌。
結(jié)合上述源代碼信不，有幾點值得注意的地方：
1）qsort的用法嘲叔，參考了：http://www.cnblogs.com/CCBB/archive/2010/01/15/1648827.html。 Tsinghua OJ 不支持 algorithm 庫抽活。
2）倒數(shù)第三行代碼（if (a[rt] == r) ans++;）實際上就是二分查找結(jié)合具體情況對答案的調(diào)整借跪。不妨分上界和下界等于或者不等于a數(shù)組中的值分情況討論，即可明白這一行的涵義酌壕。這也跟二分查找?guī)讉€細(xì)節(jié)的處理相統(tǒng)一掏愁。
3）二分查找函數(shù)中這一行：mid = left + ((right - left) >> 1);。一方面卵牍，位運算提高運算效率果港；另一方面，不直接用 (left + right) >> 1 防止計算過程中數(shù)字越界糊昙，進(jìn)而導(dǎo)致數(shù)組下標(biāo)越界辛掠。
4）二分查找不要用遞歸形式。一是提高效率释牺；二是防止堆棧溢出萝衩。
