資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C語言程式中的二分查詢（遞迴和迭代）
二分查詢是一種搜尋演算法，用於在已排序的陣列中查詢元素（目標值）的位置。在應用二分查詢之前，陣列必須已排序。
二分查詢也稱為對數搜尋、二分切分、半區間搜尋。
二分查詢的工作原理
二分查詢演算法的工作原理是將要搜尋的元素與陣列的中間元素進行比較，並根據此比較結果遵循所需的步驟。
情況1 − 元素 = 中間元素，找到元素，返回索引。
情況2 − 元素 > 中間元素，從中間元素+1索引到n的子陣列中搜索元素。
情況3 − 元素 < 中間元素，從0索引到中間元素 -1的子陣列中搜索元素。
演算法
引數初始值、結束值
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.
二分查詢演算法函式的實現會反覆呼叫函式本身。此呼叫可以分為兩種型別：
- 迭代
- 遞迴
迭代呼叫是指多次迴圈執行相同的程式碼塊。
遞迴呼叫是指反覆呼叫同一個函式。
使用迭代呼叫實現二分查詢的C程式
#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
使用遞迴呼叫實現二分查詢的C程式
#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
更新於： 2024年6月26日
76K+ 瀏覽量
廣告