如果一个算法用常数时间(O(1))将问题的大小消减为某一部分的(通常1/2),那么该算法就是O(logN).另一方面,如果使用常数时间只是把问题减少一个常数,那么该算法就是O(N).
对分查找:
#include <stdio.h>
#include <stdlib.h>
int BinarySearch(const int A[],int X,int N)
{
int Low,Mid,High;
Low=0;
High=N-1;
while(Low<=High)
{
Mid=(Low+High)/2;
printf("(Low+High)/2;%d,Low %d,High %d\n",Mid,Low,High);
if(A[Mid]<X)
{
Low=Mid+1;
printf("Low;%d\n",Low);
}
else
{
if(A[Mid]>X)
{
High=Mid-1;
printf("High;%d\n",High);
}
else
{
printf("Mid;%d\n",Mid);
return Mid;
}
}
}
return -1;
}
int main()
{
int number[]={1,4,10,15,16};
int data=0;
printf("start ....\n");
data=BinarySearch(number,4,5);
printf("下标是:%d\n",data);
exit(0);
}
运行
start ....
(Low+High)/2;2,Low 0,High 4
High;1
(Low+High)/2;0,Low 0,High 1
Low;1
(Low+High)/2;1,Low 1,High 1
Mid;1
下标是:1
欧几里德算法
两个整数的最大公因数是同时整除二者的最大整数。
#include <stdio.h>
#include <stdlib.h>
int Gcd(unsigned int M,unsigned int N)
{
unsigned int Rem;
while(N>0)
{
Rem=M%N;
M=N;
N=Rem;
}
return M;
}
int main()
{
int number[]={1,4,10,15,16};
int data=0;
printf("start ....\n");
data=Gcd(4,5);
printf("Gcd:%d\n",data);
exit(0);
}
运算
start ....
Gcd:1