运行时间中的对数

如果一个算法用常数时间(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