编辑“︁C 语言数组搜索”︁（章节）

== C语言数组搜索 ==

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

=== 基本概念 ===
数组搜索指在给定数组<code>arr[]</code>中查找目标值<code>key</code>的过程，主要包含两个关键指标：
* '''搜索成功'''：返回目标元素的索引位置（通常从0开始）
* '''搜索失败'''：返回特殊标记（如-1或<code>NULL</code>）

数学表示为：<math>\text{Search}(arr, n, key) \rightarrow \begin{cases} 
i & \text{if } arr[i] = key \\ 
-1 & \text{otherwise}
\end{cases}</math>

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

==== 代码示例 ====
<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>

'''输出：'''
<pre>
元素 16 的位置索引: 4
</pre>

==== 复杂度分析 ====
* 时间复杂度：O(n)
* 空间复杂度：O(1)

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

==== 算法原理 ====
<mermaid>
graph TD
    A[初始化 low=0, high=n-1] --> B{low ≤ high?}
    B -->|是| C[mid = (low+high)/2]
    C --> D{arr[mid] == key?}
    D -->|是| E[返回 mid]
    D -->|否| F{arr[mid] < key?}
    F -->|是| G[low = mid + 1]
    F -->|否| H[high = mid - 1]
    G --> B
    H --> B
    B -->|否| I[返回 -1]
</mermaid>

==== 代码示例 ====
<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>

'''输出：'''
<pre>
元素 18 的位置索引: 3
</pre>

==== 复杂度分析 ====
* 时间复杂度：O(log n)
* 空间复杂度：O(1)

=== 实际应用案例 ===
'''情景：'''学生成绩管理系统需要快速查询特定分数段的学生

<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>

'''输出：'''
<pre>
及格学生（分数>=70）:
学号: 103, 分数: 72
学号: 102, 分数: 88
学号: 105, 分数: 91
</pre>

=== 算法选择指南 ===
{| class="wikitable"
|+ 搜索算法对比
! 算法 !! 适用条件 !! 时间复杂度 !! 空间复杂度
|-
| 线性搜索 || 未排序数组 || O(n) || O(1)
|-
| 二分搜索 || 已排序数组 || O(log n) || O(1)
|}

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

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

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

[[Category:编程语言]]
[[Category:C]]
[[Category:C 语言数组]]