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

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

作者:用户 来源:互联网 时间:2017-12-01 09:05:20

学习查找二分不会略知一二

这两天对二分查找的学习,从完全不会到略知一二 - 摘要: 本文讲的是这两天对二分查找的学习,从完全不会到略知一二, 二分查找,顾名思义,就是快速找到你需要的元素,时间复杂度很低... 当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。我们可以使用快排法,对一组数据进行一下排序。 下面是简单的排序方法。 /*char ch[20]="sda

二分查找,顾名思义,就是快速找到你需要的元素,时间复杂度很低...

当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。我们可以使用快排法,对一组数据进行一下排序。

下面是简单的排序方法。

/*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),

比如,当一个数组很大时,需要你查找其中的一个数,你如果就直接for循环下去的话,肯定是要超时的。但是,你可另数组的开头,也就是第一个数据为的下标为low,low=0或者1,要看情况,然后最后的那个数据下标就另end=n-1,然后mid=(low+end)/2;

判断a[mid]与要查找的数据是否相等,如果相等就找到,跳出循环,没找到的话,继续循环,看目标数据下标和mid的大小,如果目标数据的下标大于mid的话,就另low=mid+1;else end=mid-1; 伪代码如下:

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;
}

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

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索学习 , 查找 , 二分 , , 不会 略知一二 ,以便于您获取更多的相关知识。

稳定可靠、可弹性伸缩的在线数据库服务,全球最受欢迎的开源数据库之一

6款热门基础云产品6个月免费体验;2款产品1年体验;1款产品2年体验

弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

开发者常用软件,超百款实用软件一站式提供