C語言數組元素查詢：無序數組線性查找與有序數組優化查找

查詢需求場景

如：學生編號數組，判斷某學號是否存在，返回下標或失敗標誌。C 標準庫無內置查詢函數，需自行實現。

1. 無序數組查詢：線性遍歷

#include <stdio.h>
#include <stdlib.h>

int main() {
    int nums[10] = {1, 10, 6, 296, 177, 23, 0, 100, 34, 999};
    int num, subscript = -1;  // -1 表示未找到
    
    printf("Please input an integer: ");
    scanf("%d", &num);
    
    for (int i = 0; i < 10; i++) {
        if (nums[i] == num) {
            subscript = i;
            break;  // 找到即退出
        }
    }
    
    if (subscript < 0)
        printf("%d isn't in the array.\n", num);
    else
        printf("%d is in the array, and its subscript is %d.\n", num, subscript);
    
    return 0;
}

運行結果

Please input an integer: 100
100 is in the array, and its subscript is 7.

Please input an integer: 28
28 isn't in the array.

關鍵點

• subscript 初始化為 -1（負數），因下標非負
• 找到即 break，避免繼續無效比較
• 時間複雜度 O(n)

2. 有序數組查詢：提前終止優化

升序數組 {0, 1, 6, 10, 23, 34, 100, 177, 296, 999}：

for (int i = 0; i < 10; i++) {
    if (nums[i] >= num) {          // 關鍵：>= 而非 ==
        if (nums[i] == num)        // 相等 → 找到
            subscript = i;
        break;                     // 否則 num < nums[i]，後續更大，不可能存在
    }
}

邏輯分析

• nums[i] >= num 兩種含義：
  • ==：找到目標，記錄下標
  • >：當前元素已大於目標，因有序，後續全大於目標 → 不存在
• 滿足條件即 break，平均比較次數減半
• 時間複雜度仍 O(n)，但常數因子更小

進階：二分查找（O(log n)）

有序數組的最優查找算法，詳見《C語言二分查找（折半查找）算法及代碼》。核心思想：每次排除一半區間。

三種查找對比

工程建議

1. 數據量 < 50：線性查找足夠
2. 數據有序且多次查詢：排序一次 + 多次二分查找 3. 高頻查詢：構建雜湊表/索引 4. 嵌入式/受限環境：優化線性查找（哨兵、展開循環）