這周練習了二分算法的題目，二分算法屬于分治算法的一種，可以用于快速周遊元素，可以将問題規模變小等等，分治算法就是分而治之，就是将較大規模的問題分解成較小規模的問題，二分算法也是，在我們 面對一種問題的時候，将他分解成了兩個問題，這樣大問題就被分解成了兩個小問題，然後這兩個小問題可以繼續分解成規模更小的問題。這大概就是二分算法的含義。
二分算法如果讓我們通俗一點去了解的話可以打個比方，比如我們查字典，并不是那種按照第一頁目錄那樣去找，而是直接翻書找字母那種，好比我要查的詞開頭單詞是s，那麼第一步我把書從中間放開，發現是字母是o，那麼s在o後面，那麼o前一半的書我就可以不管了，然後我再在o之後的部分的中間将這本書分開，看見是字母u那麼判斷，s在u之前，那麼u之後的部分我就不需要考慮了，我下面再在o和u的中間把樹翻開，這樣找到了s，所謂二分就是不斷地将問題規模變小，直到達成自己的目的為止。就是那種不達目的據不罷休的那種感覺。
如果是用二分法找某一個數，那麼二分法的模闆是下面這樣
left=1；//左邊界
right=n；//右邊界
while(left<=right)
{
mid=(left+right)/2;
if(a[mid]<=x)
left=mid+1;
else right=mid-1;
}
//不斷變更左右邊界，模拟二分過程
二分算法還可以用來進行快速排序，速度非常快，當時缺點就是不太穩定，模闆如下
void qsort(int le,int ri)
{
int i=le,j=ri;
int mid=a[(le+ri)/2];
while(i<=j)
{
while(a[i]>mid) i++;
while(a[j]<mid) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;
j--;
}
}
if(le<j) qsort(le,j);
if(i<ri) qsort(i,ri);
}
至于二分算法用來将問題規模變小的那種方法就可以通過第一種模闆，就是找某個數的模闆上加以演化即可
下面附上幾道我最近做的vj的二分算法的題目
A new e-mail service "Berlandesk" is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that's why they ask you to help. You're suggested to implement the prototype of site registration system. The system should work on the following principle.
Each time a new user wants to register, he sends to the system a request with his name. If such a namedoes not exist in the system database, it is inserted into the database, and the user gets the response OK, confirming the successful registration. If the name already exists in the system database, the system makes up a new user name, sends it to the user as a prompt and also inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another to name (name1, name2, ...), among these numbers the least i is found so that name idoes not yet exist in the database.
Input
The first line contains number n (1 ≤ n ≤ 105). The following n lines contain the requests to the system. Each request is a non-empty line, and consists of not more than 32 characters, which are all lowercase Latin letters.
Output
Print n lines, which are system responses to the requests: OK in case of successful registration, or a prompt with a new name, if the requested name is already taken.
Examples
Input
4
abacaba
acaba
abacaba
acab
Output
OK
OK
abacaba1
OK
Input
6
first
first
second
second
third
third
Output
OK
first1
OK
second1
OK
third1 這個題目後來查閱了一下資料知道是cf一道c題，其實做出來還挺驚喜的，因為除了愚人節的比賽，還有有一場比賽我能ac到c題，是以以後還是多多挑戰一下，其實有的時候不行不是真的不行，隻是我覺得我不行 ，下次還是要敢做
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long i,n,count=0,a[100000]={0},flag;
char str[50],ch[100000][50];
main()
{
cin>>n;
while(n--)
{
flag=0;
cin>>str;
for(i=0;i<=count;i++)
if(strcmp(str,ch[i])==0)
{
a[i]++;
flag=1;
break;
}
if(flag==0)
{
strcpy(ch[count],str);
count++;
cout<<"OK"<<endl;
}
else{
cout<<str<<a[i]<<endl;
}
}
}
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
這個題目的話就是，先分别求出前兩列後兩列的所有的和，然後對後兩列的和進行排序，對後兩列進行二分查找看有多少種情況即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[5010][6];
int s1[16000100];
int s2[16000100];
int n,k2=1;
int sum;
void judge(int a1)
{
int st=1;
int en=k2;
while(st<=en)
{
int l=(st+en)/2;
if(s2[l]==a1)
{
sum++;
for(int i=l+1;i<=k2;++i)
if(s2[i]==a1)
sum++;
else break;
for(int i=l-1;i>0;--i)
if(s2[i]==a1)
sum++;
else break;
return;
}
else if(a1<s2[l])
{
en=l-1;
}
else
{
st=l+1;
}
}
}
int main()
{
while(cin>>n)
{
int k1=1;
for(int i=1; i<=n; ++i)
for(int j=1; j<=4; ++j)
cin>>a[i][j];
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
s1[k1++]=a[i][1]+a[j][2];
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
s2[k2++]=a[i][3]+a[j][4];
sum=0;
sort(s2+1,s2+k2);
k2--;
for(int i=1; i<k1; ++i)
{
judge(-s1[i]);
}
printf("%d\n",sum);
}
}
Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!
Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.
Input
The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )
Output
For each test case, output the median in a separate line.
Sample Input
4
1 3 2 4
3
1 10 2
Sample Output
1
8 這個題目一開始做的時候覺得思路并不是很清晰，後來一直在紙上随便寫寫畫畫然後靈機一動，知道了思路就是判斷小于等于mid的數是否大于所有絕對值個數的一半這一步
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MT(a,b) memset(a,0,sizeof(a))
#define ll long long
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int n,m;
bool check(int x)
{
int sum=0;
for(int i=0;i<n-1;i++)
{
int p=upper_bound(a,a+n,a[i]+x)-a;
sum+=p-i-1;
}
return sum>=(m+1)/2;
}
int main()
{
while(cin>>n)
{
for(int i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
m=n*(n-1)/2;
int l=0,r=a[n-1]-a[0],ans=(l+r)/2;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
}
return 0;
}
經過這麼長時間學習了，就是總有感覺自己确實付出了很多，但卻是自己做的還不夠就是繼續努力吧，幹！
![快速排序算法C++實作（超詳細解析！！！！）一、前言二、快速排序三、AC代碼 四、共勉[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)