阿摩線上測驗
四、使用 C 語言或 Java 語言，撰寫一個叫作 linearSearch 的遞迴（recursive）線性搜尋 法函數，此函數有下列幾個參數：key（整數的搜尋鍵）、data（整數的陣列）、 start（搜尋範圍的起始位置）、end（搜尋範圍的結束位置）。如果搜尋鍵在陣列中 出現，則此函數傳回搜尋鍵在陣列中的位置。如果搜尋鍵不在陣列中出現，則此函 數傳回 -1。（30 分）
詳解 (共 2 筆)
詳解
使用 C 語言實現的 linearSearch 遞迴函數。這個函數將遍歷給定陣列的一個範圍（從 start 到 end），尋找匹配的 key 值。如果找到了 key，函數返回 key 在陣列中的位置；如果沒找到，返回 -1。
c
Copy code
#include <stdio.h>
Copy code
#include <stdio.h>
// 函數聲明
int linearSearch(int key, int data[], int start, int end);
int linearSearch(int key, int data[], int start, int end);
int main() {
int data[] = {3, 6, 8, 12, 14, 17, 25, 29, 31, 36, 42, 47, 53, 55, 62};
int n = sizeof(data) / sizeof(data[0]);
int key = 31;
int data[] = {3, 6, 8, 12, 14, 17, 25, 29, 31, 36, 42, 47, 53, 55, 62};
int n = sizeof(data) / sizeof(data[0]);
int key = 31;
// 呼叫 linearSearch 函數
int result = linearSearch(key, data, 0, n-1);
int result = linearSearch(key, data, 0, n-1);
if (result != -1) {
printf("元素 %d 出現在陣列的位置：%d\n", key, result);
} else {
printf("元素 %d 未在陣列中找到。\n", key);
}
printf("元素 %d 出現在陣列的位置：%d\n", key, result);
} else {
printf("元素 %d 未在陣列中找到。\n", key);
}
return 0;
}
}
// 函數定義
int linearSearch(int key, int data[], int start, int end) {
// 如果結束位置小於起始位置，表示範圍無效，返回 -1
if (end < start) {
return -1;
}
// 檢查起始位置的元素是否是搜尋鍵
if (data[start] == key) {
return start;
}
// 否則，遞迴調用函數本身，對範圍中的下一個元素進行檢查
return linearSearch(key, data, start + 1, end);
}
在這個實現中，linearSearch 函數會遞迴地檢查每個元素，直到找到匹配的元素或者檢查完所有元素。這種方法雖然簡單易懂，但在大型數據集上可能不是最高效的搜索策略，特別是對於已排序的數據集，二分搜尋法（Binary Search）會是更好的選擇。然而，對於未排序的數據集或需要執行少量搜尋操作的情況，線性搜尋是一種實用的解決方案。
int linearSearch(int key, int data[], int start, int end) {
// 如果結束位置小於起始位置，表示範圍無效，返回 -1
if (end < start) {
return -1;
}
// 檢查起始位置的元素是否是搜尋鍵
if (data[start] == key) {
return start;
}
// 否則，遞迴調用函數本身，對範圍中的下一個元素進行檢查
return linearSearch(key, data, start + 1, end);
}
在這個實現中，linearSearch 函數會遞迴地檢查每個元素，直到找到匹配的元素或者檢查完所有元素。這種方法雖然簡單易懂，但在大型數據集上可能不是最高效的搜索策略，特別是對於已排序的數據集，二分搜尋法（Binary Search）會是更好的選擇。然而，對於未排序的數據集或需要執行少量搜尋操作的情況，線性搜尋是一種實用的解決方案。
詳解
我們今天要學習的是遞迴式的線性搜尋，也就是用程式找到特定值在一個陣列中的位置。這個題目要求我們撰寫一個叫作 linearSearch 的函數，它會有幾個參數：key（我們要找的數值）、data（一個整數陣列）、start 和 end（代表我們要搜尋的範圍）。
遞迴的概念是什麼呢？簡單來說，遞迴是指一個函數自己呼叫自己。我們的 linearSearch 函數會從陣列的 start 位置開始尋找，檢查這個位置上的數字是不是我們要找的 key，如果不是，它會呼叫自己來檢查下一個位置，直到找到符合的數字或者到達 end 結束。如果到最後都找不到，那麼我們就會回傳 -1。
選項的正確與錯誤原因：
- 如果 key 存在於陣列中，函數會找到並回傳它的索引位置。
- 如果 key 不存在，函數會一直搜索到最後一個位置並回傳 -1
正在搜尋的範圍: 從 0 到 6
索引 0 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 1 到 6
索引 1 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 2 到 6
索引 2 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 3 到 6
索引 3 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 4 到 6
找到搜尋鍵 19 在索引 4
搜尋結果: 4
索引 0 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 1 到 6
索引 1 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 2 到 6
索引 2 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 3 到 6
索引 3 上的數值不是 19，繼續搜尋
正在搜尋的範圍: 從 4 到 6
找到搜尋鍵 19 在索引 4
搜尋結果: 4