算法之二分查找(c语言版实现+测试)

递归算法(deep是为了测试,实际生产不需要): 核心算法:

//递归算法 int rank(Type key,Type a[],int lo,int hi,int deep) { if(lo > hi) return -1; int mid = lo + (hi - lo) / 2; printf("deep: %d lo: %d hi: %d\n",deep,lo,hi); if (key > a[mid]) { ++deep; return rank(key,a,mid + 1,hi,deep); } else if (key < a[mid]) { ++deep; return rank(key,a,lo,mid - 1,deep); } else return mid; } int BinarySearch(Type key,Type a[],int length) { int deep = 0; return rank(key,a,0,length,deep); }

辅助排序函数（快速排序):

void QuickSort(Type a[],int left,int right) { Type temp; if(left < right) { int i = left; int j = right; temp = a[left]; do { while(i < j && a[j] > temp) --j; if(i < j) a[i++] = a[j]; while(i < j && a[i] < temp) ++i; if(i < j) a[j--] = a[i]; }while(i != j); a[i] = temp; QuickSort(a,left,i-1); QuickSort(a,i + 1,right); } }

测试代码:

void test(char *mode,char *file) { //得到test 数组 FILE *fp; if ((fp = fopen(file,"r")) == NULL) { return; } int count = 0; int temp; while (fscanf(fp,"%d",&temp) != EOF) ++count; fseek(fp,0,SEEK_SET); Type a[count]; int pos = 0; while(fscanf(fp,"%d",&a[pos++]) != EOF); QuickSort(a,0,count - 1); Type key; if(strcmp(mode,"exist") == 0) { while(scanf("%d",&key) != EOF) { if(BinarySearch(key,a,sizeof(a)/sizeof(Type)-1) != -1) { printf("the key %d is exist in %s\n",key,file); } } } if(strcmp(mode,"noexist") == 0) { while(scanf("%d",&key) != EOF) { if(BinarySearch(key,a,sizeof(a)/sizeof(Type)-1) != -1) { printf("the key %d is not exist in %s\n",key,file); } } } }

main.c

int main() { test("exist","test.txt"); return 0; }

非递归算法:

//非递归算法 int BinarySearch(Type key,Type a[],int hi) { int lo = 0; while(lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] > key) hi = mid - 1; else if (a[mid] < key) lo = mid + 1; else return mid; } return -1; }

辅助排序函数(快速排序):

void QuickSort(Type a[],int left,int right) { Type temp; if(left < right) { int i = left; int j = right; temp = a[left]; do { while(i < j && a[j] > temp) --j; if(i < j) a[i++] = a[j]; while(i < j && a[i] < temp) ++i; if(i < j) a[j--] = a[i]; }while(i != j); a[i] = temp; QuickSort(a,left,i-1); QuickSort(a,i + 1,right); } }

测试代码:

void test(char *mode,char *file) { //得到test 数组 FILE *fp; if ((fp = fopen(file,"r")) == NULL) { return; } int count = 0; int temp; while (fscanf(fp,"%d",&temp) != EOF) ++count; fseek(fp,0,SEEK_SET); Type a[count]; int pos = 0; while(fscanf(fp,"%d",&a[pos++]) != EOF); QuickSort(a,0,count - 1); Type key; if(strcmp(mode,"exist") == 0) { while(scanf("%d",&key) != EOF) { if(BinarySearch(key,a,sizeof(a)/sizeof(Type)-1) != -1) { printf("the key %d is exist in %s\n",key,file); } } } if(strcmp(mode,"noexist") == 0) { while(scanf("%d",&key) != EOF) { if(BinarySearch(key,a,sizeof(a)/sizeof(Type)-1) != -1) { printf("the key %d is not exist in %s\n",key,file); } } } }

main.c

int main() { test("exist","test.txt"); return 0; }