1. 云栖社区>
2. PHP教程>
3. 正文

# 这两天对二分查找的学习，从完全不会到略知一二

`/*char ch[20]="sdasdacsdasdas";cout<<ch<<endl;sort(ch,ch+14);cout<<ch<<endl*/     升序方法 头文件   #include<algorithm>`

`降序`
`#include<iostream>#include<algorithm>using namespace std;bool cmp (const int a, const int b){    return a > b;}int main(){    int data[5];    for(int i = 0; i < 5; i++)        cin >> data[i];    sort(data, data + 5, cmp);    return 0;}`

二分排序最大的好处就是时间复杂度小O(log2n)，

l=0;
r=n-1;
while(r>=l)
{
mid=(l+r)/2;
if(x[mid]-x[i]>k)
r=mid-1;
else
l=mid+1;

}

hdu 5178

Problem DescriptionJohn has n points on the X axis, and their coordinates are (x[i],0),(i=0,1,2,…,n−1). He wants to know how many pairs<a,b> that |x[b]−x[a]|≤k.(a<b) InputThe first line contains a single integer T (about 5), indicating the number of cases.
Each test case begins with two integers n,k(1≤n≤100000,1≤k≤109).
Next n lines contain an integer x[i](−109≤x[i]≤109), means the X coordinates. OutputFor each case, output an integer means how many pairs<a,b> that |x[b]−x[a]|≤k. Sample Input25 5-10001001011025 300-1000100101102 Sample Output310 题意是找出两个数，判断这两个数的差的绝对值是否<=k，求一共有多少对这样的数， 如果一个个查找的话，肯定超时咯，所以就用二分法，代码如下：

#include <iostream>
#include<algorithm>
using namespace std;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {

long long n,k,x[100005],i,t;
long long r,mid,l,ans;
cin>>t;

while(t--)
{
cin>>n>>k;
for(i=0;i<n;i++)
cin>>x[i];
sort(x,x+n);
l=0;
r=n-1;
ans=0;
for(i=0;i<n;i++)//一项一项判断
{
l=i+1;
r=n-1;

while(r>=l)//二分查找
{
mid=(l+r)/2;
if(x[mid]-x[i]>k)
r=mid-1;
else
l=mid+1;

}
ans=ans+r-i;
}
cout<<ans<<endl;
}

return 0;
}

*********************

40+云计算产品，6个月免费体验