C 语言数组搜索

C语言数组搜索[编辑 | 编辑源代码]

数组搜索是C语言中处理数组数据时的核心操作之一，指在数组中查找特定元素或满足条件的元素的过程。本条目将详细介绍线性搜索、二分搜索等经典算法，并分析其适用场景与性能差异。

基本概念[编辑 | 编辑源代码]

数组搜索指在给定数组arr[]中查找目标值key的过程，主要包含两个关键指标：

搜索成功：返回目标元素的索引位置（通常从0开始）
搜索失败：返回特殊标记（如-1或NULL）

数学表示为： $Search (a r r, n, k e y) \to {\begin{cases} i & if a r r [i] = k e y \\ - 1 & otherwise \end{cases}$

线性搜索[编辑 | 编辑源代码]

最基础的搜索方法，逐个遍历数组元素直到找到目标。

代码示例[编辑 | 编辑源代码]

#include <stdio.h>

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;  // 找到则返回索引
        }
    }
    return -1;  // 未找到
}

int main() {
    int data[] = {24, 18, 12, 9, 16, 66};
    int size = sizeof(data) / sizeof(data[0]);
    int target = 16;
    
    int result = linearSearch(data, size, target);
    printf("元素 %d 的位置索引: %d\n", target, result);
    return 0;
}

输出：

元素 16 的位置索引: 4

复杂度分析[编辑 | 编辑源代码]

时间复杂度：O(n)
空间复杂度：O(1)

二分搜索[编辑 | 编辑源代码]

仅适用于已排序数组的高效搜索算法，通过不断缩小搜索范围来定位元素。

算法原理[编辑 | 编辑源代码]

代码示例[编辑 | 编辑源代码]

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防止溢出
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    int sortedData[] = {9, 12, 16, 18, 24, 66};
    int size = sizeof(sortedData) / sizeof(sortedData[0]);
    int target = 18;
    
    int result = binarySearch(sortedData, size, target);
    printf("元素 %d 的位置索引: %d\n", target, result);
    return 0;
}

输出：

元素 18 的位置索引: 3

复杂度分析[编辑 | 编辑源代码]

时间复杂度：O(log n)
空间复杂度：O(1)

实际应用案例[编辑 | 编辑源代码]

情景：学生成绩管理系统需要快速查询特定分数段的学生

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

// 结构体存储学生信息
typedef struct {
    int id;
    int score;
} Student;

// 比较函数用于qsort
int compareScores(const void *a, const void *b) {
    return ((Student*)a)->score - ((Student*)b)->score;
}

// 在排序后的数组中查找分数>=threshold的第一个学生
int findFirstPassing(Student arr[], int n, int threshold) {
    int left = 0, right = n - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid].score >= threshold) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

int main() {
    Student classA[5] = {{101, 65}, {102, 88}, {103, 72}, {104, 59}, {105, 91}};
    int classSize = 5;
    int passingScore = 70;
    
    qsort(classA, classSize, sizeof(Student), compareScores);
    int firstPass = findFirstPassing(classA, classSize, passingScore);
    
    if (firstPass != -1) {
        printf("及格学生（分数>=%d）:\n", passingScore);
        for (int i = firstPass; i < classSize; i++) {
            printf("学号: %d, 分数: %d\n", classA[i].id, classA[i].score);
        }
    } else {
        printf("没有及格学生\n");
    }
    return 0;
}

输出：

及格学生（分数>=70）:
学号: 103, 分数: 72
学号: 102, 分数: 88
学号: 105, 分数: 91

算法选择指南[编辑 | 编辑源代码]

搜索算法对比
算法	适用条件	时间复杂度	空间复杂度
线性搜索	未排序数组	O(n)	O(1)
二分搜索	已排序数组	O(log n)	O(1)

进阶技巧[编辑 | 编辑源代码]

哨兵值优化：线性搜索中可减少比较次数
插值搜索：适用于均匀分布的已排序数组
哈希表实现：O(1)时间复杂度但需要额外空间

常见错误[编辑 | 编辑源代码]

二分搜索时未检查数组是否已排序
忽略数组边界条件（如空数组）
整数溢出风险：mid = (low + high)/2应写为low + (high - low)/2

练习建议[编辑 | 编辑源代码]

1. 实现递归版本的二分搜索 2. 编写函数统计数组中特定值的出现次数 3. 设计处理字符串数组的搜索函数