二分查找

一 : 二分查找 (递归实现)

1  显示效果:

2  代码

#include "windows.h" #include "iostream" using namespace std; void FindKey(int * a ,int start, int end , int key) { int i = start; int j = end; int middle = (j+i)/2; if (end < start) { printf("没有找到该数%d\n",key); return; } if (a[middle] == key ) { printf("找到该数%d\n",key); return; } else if (a[middle] > key) { end = middle-1;//不能写成 end = middle FindKey(a, start, end, key); } else if (a[middle] < key) { start = middle+1;//不能写成 start = middle+1; FindKey(a, start, end, key); } } void main() { int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9,11 }; FindKey(a, 0, sizeof(a) / sizeof(int)-1, 113); FindKey(a, 0, sizeof(a) / sizeof(int)-1, 11); FindKey(a, 0, sizeof(a) / sizeof(int)-1, 10); system("pause"); }

二  二分法查找(非递归)

1 显示效果

2  代码

#include"stdio.h" void search(int *a , int len , int key) { int low = 0; int high = len - 1; int mid = (low + high) / 2; /*if (key<a[low] || key > a[high]) { printf("未找到该数%d\n",key); return; } if (key == a[low] || key == a[high]) { printf("找到该数%d\n",key); return; }这些注释掉的判断没有用*/ while (low<=high) { if (a[mid] == key) { printf("找到该数%d\n",key); return; } else if (a[mid] < key) { low = mid+1;//这里不能写成low = mid mid = (low + high) / 2; } else if (a[mid]>key) { high = mid-1; mid = (low + high) / 2; } } printf("未找到该数%d\n", key); } void main() { int a[10] = {1,2,3,4,5,6,7,8,9,11}; printf("非递归实现二分法查找\n"); search(a, sizeof(a) / sizeof(int), 11); search(a, sizeof(a) / sizeof(int), 10); search(a, sizeof(a) / sizeof(int), 3); getchar(); }