二分查找,是一种针对有序序列的查找方式,每次迭代会缩小一半的查找范围,一次查找的时间复杂度为O(logN)。
简单说一下二分查找过程:在有序序列seq[]中找一个数n,假设这个序列的起始下标分别为a,b,mid=(a+b)/2,那么n要么就是seq[mid](n=seq[mid]),要么在mid左边(n<seq[mid]),要么在mid右边(n>seq[mid]),要么这个数根本不在seq[]中。
下面这道题是二分查找的典型应用:
zoj1101
题意描述:在给定整数序列(<=1000)中找出四个不同的数,使得三个数的和等于另外一个数。
直接用四层循环铁定超时,这里采用了一种拿空间换时间的方式。
假设有a+b+d=c,这等价于a+b=c-d,我们可以把所有的a+b存起来(<=10^6个),把所有的c-d也存起来(<=10^6个),当拿到每一个a+b时我们只需要在所有c-d的序列中查找就行了。先把c-d序列排序,排序时间复杂度O(NlogN),查找过程可以用二分,这样就不会超时啦。
以下是本题代码:
#include<stdio.h>
#include<stdlib.h>
#define MAX 2100000000
#define LEN 1000010
#define LEN1 1010
typedef struct
{
int rs;
int a;
int b;
}Node;
Node addseq[LEN];
Node subseq[LEN];
int num[LEN1];
int seqlen;
int wagamount;
int binSch(int n, int bg, int ed)//二分查找——递归方式
{
if(bg > ed)
return -1;
if(bg == ed)
{
if(n == subseq[bg].rs)
return bg;
return -1;
}
int mid = (bg + ed) / 2;
if(n == subseq[mid].rs)
return mid;
if(n < subseq[mid].rs)
return binSch(n, bg, mid - 1);
if(n > subseq[mid].rs)
return binSch(n, mid + 1, ed);
}
int binSch2(int n, int bg, int ed)//二分查找——非递归方式
{
while(bg <= ed)
{
int mid = (bg + ed) / 2;
if(n == subseq[mid].rs)
return mid;
if(n < subseq[mid].rs)
ed = mid - 1;
else
bg = mid + 1;
}
return -1;
}
int findWinner()
{
int i, j;
int n;
for(i = 0; i < seqlen; i++)
{
n = addseq[i].rs;
int a = addseq[i].a;
int b = addseq[i].b;
int find = binSch(n, 0, seqlen - 1);
if(find != -1)
{
int c = subseq[find].a;
int d = subseq[find].b;
if(a != b && a != c && a != d && b != c && b != d && c != d)
{
if(c > wagamount)
wagamount = c;
}
}
}
}
int cmp(const void *a, const void *b)
{
Node *a0 = (Node*)a;
Node *b0 = (Node*)b;
return a0 -> rs - b0 -> rs;
}
int main()
{
int i, j;
int n;
scanf("%d", &n);
while(n != 0)
{
for(i = 0; i < n; i++)
scanf("%d", &num[i]);
seqlen = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(j != i)
{
addseq[seqlen].rs = num[i] + num[j];
addseq[seqlen].a = num[i];
addseq[seqlen].b = num[j];
subseq[seqlen].rs = num[i] - num[j];
subseq[seqlen].a = num[i];
subseq[seqlen].b = num[j];
seqlen++;
}
qsort(subseq, seqlen, sizeof(Node), cmp);
wagamount = -MAX;
findWinner();
if(wagamount != -MAX)
printf("%d\n", wagamount);
else
printf("no solution\n");
scanf("%d", &n);
}
//system("pause");
}
posted on 2012-08-01 21:39
小鼠标 阅读(1043)
评论(0) 编辑 收藏 引用 所属分类:
数据结构