二分查找算法是在有序数组中用到的较为频繁的一种算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为O(n).但二分查找算法则更优，因为其查找时间为O(lgn)，譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：
1. 第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找。
2. 寻找{6， 7， 8， 9}的中位数，为7，7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。
3. 二分查找算法就是不断将数组进行对半分割，每次拿中间元素和goal进行比较。
注意：必须是一组排列有序的数值。
具体实现过程：
#include <stdio.h>
void search(int *a,int num,int n); int main() { int a[] = {10 ,4,5,60,90,100,3,55}; int n = sizeof(a)/sizeof(int); int i,j; for(i = 0;i<n-1;i++) { for(j = 0;j<n-1-i;j++) { if(a[j]>a[j+1]) { int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } } for(i = 0;i<n;i++) { printf("%4d",a[i]); } printf("\n"); int num; while(1) { printf("请输入你要查找的数字：\n"); scanf("%d",&num); search(a,num,n); }
return 0; }
void search(int *a,int num,int n) { int left = 0; int right = n-1; int mid = (left + right)/2;
while(a[mid] != num &&left < right) { if(a[mid]>num) { right = mid -1; } else if (a[mid] < num) { left = mid + 1; } mid = (left + right)/2; } if(a[mid] == num) { printf("查找后的值：%d\n",a[mid]); } else { printf("查找不到\n"); }
} |