二分查找的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。

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

Primeshot

专业级AI人像摄影工作室

下载

为了实现二分查找，我们可以用两种方式编写代码。这两种方式仅与我们调用检查二分搜索元素的函数的方式不同。它们是：

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

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

示例

#include
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,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
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,RecursiveBsearch(A,0,9,n));
   return 0;
}

输出

55 is found at Index 8