二进制搜索的C程序（递归和迭代）？

二进制搜索算法是一种基于比较和拆分机制的算法。二进制搜索算法也称为半间隔搜索，对数搜索或二进制印章。二进制搜索算法，在排序数组中搜索目标值的位置。它将目标值与数组的中间元素进行比较。如果元素等于目标元素，则算法返回找到的元素的索引。如果它们不相等，则搜索算法将使用该数组的一半部分，根据值的比较，该算法将使用上半部分（值小于中间值）和后半部分（当值大于中间值时）。并为下一个数组做同样的事情。

Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8

说明

对于我们的阵列-

我们将比较55和数组的中间元素18，它小于55，因此我们将使用数组的后半部分，即数组{24，45，55，99}，中间的也是55。用它检查搜索元素的值。并匹配该值，则我们将返回该值的索引为8。

如果搜索元素比中间元素小，那么我们将继续使用前半部分，直到搜索元素在数组中间找到为止。

为了实现二进制搜索，我们可以通过两种方式编写代码。这两种方式仅以我们调用检查二进制搜索元素的函数的方式进行延迟。他们是：

• 使用迭代-这意味着在函数内部使用循环来检查中间元素的相等性。

• 使用此方法时，函数会使用一组不同的值一次又一次地调用自身。

示例

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
   int A[] = {0,12,6,12,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n));
   return 0;
}
int iterativeBsearch(int A[], int size, int element) {
   int start = 0;
   int end = size-1;
   while(start<=end) {
      int mid = (start+end)/2;
      if( A[mid] == element) {
         return mid;
      } else if( element < A[mid] ) {
         end = mid-1;
      } else {
         start = mid+1;
      }
   }
   return -1;
}

输出结果

55 is found at Index 8

示例

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
   if(start>end) return -1;
      int mid = (start+end)/2;
   if( A[mid] == element ) return mid;
   else if( element < A[mid] )
      RecursiveBsearch(A, start, mid-1, element);
   else
      RecursiveBsearch(A, mid+1, end, element);
}
int main() {
   int A[] = {0,2,6,11,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n));
   return 0;
}

输出结果

55 is found at Index 8