个人原创，转载请注明出处，谢谢！ 一、目的 input: 有序序列 output: 查找结果，如果为-1则未找到目标 constrain: 使用两分法进行查找，使查找时间复杂度为O(logn) 二、 算法原理  两分搜索算法是一种理解比较简单，但执行效率却十分高的算法。可以用循环的方式来实现，也可以用递归的方式来实现。算法原理如图:      通过不断的改变l和u的值来接近要查找的目标值（40） m = ( 0 + 13 ) / 2 = 6  result: l = 0, u = m – 1 = 5 m = ( 0 + 5 ) / 2 = 2  result: l = m + 1 = 3, u = 5 m = ( 3 + 5 ) / 2 = 4  result: l = 3 , u = m – 1 = 3   三、代码 #include <stdio.h> #include <stdlib.h> #include <time.h>   #define MAXN 1000000 typedef int DataType; DataType x[MAXN]; int n = 0;   int binarysearch (DataType t) {      int l, u, m;        l = 0;        u = n-1;        while (l <= u) {               m = (l + u) / 2;               if (x[m] < t)                      l = m+1;               else if (x[m] == t)                      return m;               else /* x[m] > t */                      u = m-1;        }        return -1; }   int main(void) {        int I, target = -1;        int result = -1;     printf(“please input n and search target number:\n” );        while (scanf("%d %d ", &n, &target) != EOF) { for (i = 0; i <= n; i++) {                      x[i] = 10*i; }                 result = binarysearch(target);               printf(“search result = %d\n”, result);        }        return 0; }   四、代码注解 #define MAXN 1000000 typedef int DataType;  /*定义数据数型，可增加算法函数的通用性*/ DataType x[MAXN]; int n = 0;   /*t为待搜索的目标值*/ int binarysearch (DataType t) {      int l, u, m;        l = 0;        u = n-1;        while (l <= u) { /*目标仍在l和u之间*/               m = (l + u) / 2;  /*折半*/               if (x[m] < t) { /*如果中间值小于目标值*/                      l = m+1;  /*l需要向u靠拢*/               } else if (x[m] == t) { /*如果等于t，则m即为要搜索的位置，返回即可*/                      return m;               } else { /*u需要向l靠拢*/                      u = m-1; }        }        return -1; /*如果走到这，说明目标不在序列内，返回失败*/ }   int main(void) {        int I, target = -1;        int result = -1;     printf(“please input n and search target number:\n” );        while (scanf("%d %d ", &n, &target) != EOF) {        /*初始化输入数组，仅作为示例*/ for (i = 0; i <= n; i++) {                      x[i] = 10*i; }                 /*调用搜索函数，并记录搜索结果*/               result = binarysearch(target);               printf(“search result = %d\n”, result);        }        return 0; }  

评论