查找算法

640阅读　0评论2014-11-14　mandagod
分类：C/C++

1. 二分查找算法

循环实现
  1. int binarySearch(int *a, int len, int x) {
  2.     int low = 0;
  3.     int high = len-1;
  4.     int mid;

  6.     while (low <= high) {
  7.         mid = (low + high) / 2;
  8.         if (a[mid] < x)
  9.             low = mid + 1;
  10.         else if (a[mid] > x)
  11.             high = mid - 1;
  12.         else {
  13.             printf("found: a[%d]=%d\n", mid, a[mid]);
  14.             return mid;
  15.         }
  16.     }
  17.     printf("notfound\n");
  18.     return -1;
  19. }
递归实现
  1. int binarySearchRecursive(int *a, int x, int low, int high) {
  2.     if (low > high)
  3.         return -1;

  5.     int mid = (low + high) / 2;
  6.     if (a[mid] < x)
  7.         return binarySearchRecursive(a, x, mid+1, high);
  8.     else if (a[mid] > x)
  9.         return binarySearchRecursive(a, x, low, mid-1);
  10.     else
  11.         return mid;
  12. }

  14. int binarySearchRecursive(int *a, int len, int x) {
  15.     int ind = binarySearchRecursive(a, x, 0, len-1);
  16.     if (ind == -1)
  17.         printf("notfound\n");
  18.     else
  19.         printf("found: a[%d]=%d\n", ind, a[ind]);
  20.     return ind;
  21. }

上一篇：排序算法集合 -3
下一篇：优先队列 - 堆