二分查找，是一种针对有序序列的查找方式，每次迭代会缩小一半的查找范围，一次查找的时间复杂度为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
小鼠标 阅读(1020)
评论(0) 编辑 收藏 引用 所属分类:
数据结构