二分查找，是一種針對有序序列的查找方式，每次迭代會縮小一半的查找范圍，一次查找的時間復雜度為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
小鼠標 閱讀(1070)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構