编辑“︁搜索算法概述”︁（章节）

== 基本概念 ==

搜索算法的核心目标是在给定的数据集中高效地找到目标值或满足条件的元素。算法的效率通常通过'''时间复杂度'''和'''空间复杂度'''来衡量。以下是两种最基本的搜索算法：

=== 1. 线性搜索（Linear Search） ===

线性搜索是最简单的搜索算法，它逐个检查数据集中的每个元素，直到找到目标值或遍历完整个数据集。

==== 算法步骤 ====
1. 从数据集的第一个元素开始。
2. 比较当前元素与目标值。
3. 如果匹配，返回当前元素的索引。
4. 如果不匹配，移动到下一个元素。
5. 如果遍历完所有元素仍未找到目标值，返回“未找到”。

==== 代码示例 ====
<syntaxhighlight lang="python">
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1  # 未找到

# 示例输入
arr = [10, 20, 30, 40, 50]
target = 30

# 调用函数
result = linear_search(arr, target)

# 输出
print(f"目标值 {target} 的索引是: {result}")  # 输出: 目标值 30 的索引是: 2
</syntaxhighlight>

==== 复杂度分析 ====
* 时间复杂度：<math>O(n)</math>，其中<math>n</math>是数据集的大小。
* 空间复杂度：<math>O(1)</math>，不需要额外空间。

=== 2. 二分搜索（Binary Search） ===

二分搜索是一种高效的搜索算法，但要求数据集是'''有序的'''。它通过反复将搜索区间分成两半来缩小范围。

==== 算法步骤 ====
1. 确定数据集的中间元素。
2. 如果中间元素等于目标值，返回其索引。
3. 如果目标值小于中间元素，在左半部分继续搜索。
4. 如果目标值大于中间元素，在右半部分继续搜索。
5. 重复直到找到目标值或区间为空。

==== 代码示例 ====
<syntaxhighlight lang="python">
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 未找到

# 示例输入（必须是有序数组）
arr = [10, 20, 30, 40, 50]
target = 40

# 调用函数
result = binary_search(arr, target)

# 输出
print(f"目标值 {target} 的索引是: {result}")  # 输出: 目标值 40 的索引是: 3
</syntaxhighlight>

==== 复杂度分析 ====
* 时间复杂度：<math>O(\log n)</math>，因为每次迭代都将搜索范围减半。
* 空间复杂度：<math>O(1)</math>。