二分法听起来并不陌生，早在高中就有提到，比如找到一段电线中那里断路就要从中间向两边找，然后在把断的那一面分成两段…这样就能节省时间了.那么在计算机中的二分法也是如此,面对庞大的数据也能很快的找出来。但在运用上灵活多变，一定要善于运用，以下是两个二分法查找的的两个题，及代码；
Description
Everyone in the HDU knows that the number of boys is larger than the number of girls. But now, every boy wants to date with pretty girls. The girls like to date with the boys with higher IQ. In order to test the boys ' IQ, The girls make a problem, and the boys who can solve the problem correctly and cost less time can date with them. The problem is that : give you n positive integers and an integer k. You need to calculate how many different solutions the equation x + y = k has . x and y must be among the given n integers. Two solutions are different if x0 != x1 or y0 != y1. Now smart Acmers, solving the problem as soon as possible. So you can dating with pretty girls. How wonderful! 
Input
The first line contain an integer T. Then T cases followed. Each case begins with two integers n(2 <= n <= 100000) , k(0 <= k < 2^31). And then the next line contain n integers.
Output
For each cases,output the numbers of solutions to the equation.
Sample Input
2
5 4
1 2 3 4 5
8 8
1 4 5 7 8 9 2 6
Sample Output
3
5
题意大概是：有T组样例输入N K，接下来输入N个数A1，A2。。Ai。。An，并且从中找的Ai+Aj=K的解（1+3=4则表示两个解）。
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; int a[100005]; int main() { int t,n,m,i,j,k; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); for(i=1; i<=n; i++) scanf("%d",&a[i]); a[0]=-1; sort(a,a+n+1); int ans=0; int big,small; int mid; for(i=1; i<=n; i++) { if(a[i-1]!=a[i]) { big=n; small=1; while(small<=big) { mid=(big+small)/2; if(a[mid]+a[i]==k) { ans++; break; } if(a[mid]+a[i]>k) big=mid-1; else small=mid+1; } } } printf("%d ",ans); } return 0; }
Description
The new semester begins! Different kinds of student societies are all trying to advertise themselves, by giving flyers to the students for introducing the society. However, due to the fund shortage, the flyers of a society can only be distributed to a part of the students. There are too many, too many students in our university, labeled from 1 to 2^32. And there are totally N student societies, where the i-th society will deliver flyers to the students with label A_i, A_i+C_i,A_i+2*C_i,…A_i+k*C_i (A_i+k*C_i<=B_i, A_i+(k+1)*C_i>B_i). We call a student "unlucky" if he/she gets odd pieces of flyers. Unfortunately, not everyone is lucky. Yet, no worries; there is at most one student who is unlucky. Could you help us find out who the unfortunate dude (if any) is? So that we can comfort him by treating him to a big meal!
Input
There are multiple test cases. For each test case, the first line contains a number N (0 < N <= 20000) indicating the number of societies. Then for each of the following N lines, there are three non-negative integers A_i, B_i, C_i (smaller than 2^31, A_i <= B_i) as stated above. Your program should proceed to the end of the file.
Output
For each test case, if there is no unlucky student, print "DC Qiang is unhappy." (excluding the quotation mark), in a single line. Otherwise print two integers, i.e., the label of the unlucky student and the number of flyers he/she gets, in a single line.
Sample Input
2
1 10 1
2 10 1
4
5 20 7
6 14 3
5 9 1
7 21 12
Sample Output
1 1
8 1
来源:HDU4768
题意：
有N个社团发传单给新生，而新生以编好学号，每个社团从第A号学生开始发，每隔C个学生再发一张，并且每个社团所发的学生的学号小于B，即：A+k*C<=B.
#include <iostream> #include <stdio.h> #include <algorithm> #define ll long long using namespace std; ll n,a[20005],b[20005],c[20005]; ll search(ll mid) { ll k,sum=0; for(int i=0; i<n; i++) { k=min(mid,b[i]); if(k>=a[i]) sum+=(k-a[i])/c[i]+1; } return sum; } int main() { while(~scanf("%d",&n)) { for(int i=0; i<n; i++) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]); ll L=0; ll R=1LL<<31; ll mid; while(L<R) { mid=(L+R)/2; if(search(mid)%2) R=mid; else L=mid+1; } if(L==1LL<<31) printf("DC Qiang is unhappy. "); else printf("%lld %lld ",L,search(L)-search(L-1)); } return 0; }