二分查找的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 </p><p>",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 </p><p>",n,RecursiveBsearch(A,0,9,n));
   return 0;
}

輸出

55 is found at Index 8

以上是二分查找的C程式（遞歸和迭代）的詳細內容。更多資訊請關注PHP中文網其他相關文章！