如果一个算法用常数时间(O(1))将问题的大小消减为某一部分的（通常1/2），那么该算法就是O（logN）.另一方面，如果使用常数时间只是把问题减少一个常数，那么该算法就是O(N).
对分查找：
给定一个整数X和整数后者已经预先排序并在内存中，求使得的下标i,如果X不在数据中，则返回i=-1.明显的算法是从左到右扫描数据，其运行花费的线性时间。然而，这个算法没有用到该表已经排序的事实，这就使得算法不是很好。一个好的策略是验证X是否居中的元素。如果是，则答案就找到了。
如果X小于居中元素，那么我们可以应用同样的策略于居中元素左侧已经排序的子序列；同理，如果X大于居中元素，那么我们检查右半部分。
#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
