二分搜尋（遞歸與迭代）在C程式中的實現

二分搜尋是一種用於在排序數組中尋找元素（目標值）位置的搜尋演算法。在應用二分搜尋之前，數組應該被排序。

二分搜尋也被稱為對數搜尋、二分查找、半區間搜尋。

工作原理

二分搜尋演算法透過將要搜尋的元素與陣列的中間元素進行比較，並根據此比較結果執行所需的過程。

情況1 - 元素 = 中間值，找到元素並傳回索引。

情況2 - 元素 > 中間值，在從中間 1索引到n的子數組中搜尋元素。

情況3 - 元素

演算法

參數初始值，結束值

Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

二分搜尋演算法的實作函數使用了重複呼叫函數。這個呼叫可以有兩種類型：

• 迭代
• 遞迴

#迭代呼叫是多次循環同一段程式碼。

遞迴呼叫是重複呼叫同一個函數。

使用迭代呼叫實現二分搜尋的程式

範例

 示範

#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
   while (start_index <= end_index){
      int middle = start_index + (end_index- start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] < element)
         start_index = middle + 1;
      else
         end_index = middle - 1;
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 16;
   int found_index = iterativeBinarySearch(array, 0, n-1, element);
   if(found_index == -1 ) {
      printf("Element not found in the array ");
   }
   else {
      printf("Element found at index : %d",found_index);
   }
   return 0;
}

輸出

Element found at index : 4

使用遞迴呼叫實作二分查找的程式

範例

 線上示範

#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
   if (end_index >= start_index){
      int middle = start_index + (end_index - start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] > element)
         return recursiveBinarySearch(array, start_index, middle-1, element);
      return recursiveBinarySearch(array, middle+1, end_index, element);
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 9;
   int found_index = recursiveBinarySearch(array, 0, n-1, element);
   if(found_index == -1 ) {
      printf("Element not found in the array ");
   }
   else {
      printf("Element found at index : %d",found_index);
   }
   return 0;
}

輸出

Element found at index : 3

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