09 查找算法：顺序查找与二分查找（算法原理、算法实现、时间和空间复杂度分析）
目录
1 顺序查找
1.1 算法原理
顺序查找（也称为线性查找）是一种基本的查找算法，适用于任何类型的数据集，尤其是未排序的数据集。其核心思想是从数据集的起始位置开始，逐个检查每个元素，直到找到首次出现的目标元素或遍历完整个数据集。
1. 从头开始遍历：从数据集的第一个元素开始，逐个访问每个元素。
2. 比较目标：对于每个访问到的元素，将其与目标元素进行比较。
3. 查找成功：如果当前元素等于目标元素，则查找成功，返回当前元素的索引。
4. 查找失败：如果遍历完整个数据集仍未找到目标元素，则查找失败，返回一个特殊的标识（通常为 -1）来表示未找到。
1.2 算法实现
#include <stdio.h>
// 顺序查找函数，返回首次出现的元素的索引
int sequentialSearch(const int arr[], int size, const int target)
{
for (int i = 0; i < size; ++i)
{
if (arr[i] == target)
{
return i; // 找到目标，返回当前元素的索引
}
}
return -1; // 未找到目标，返回标识
}
int main()
{
// 定义一个示例数组，包含重复元素
int arr[] = {4, 2, 8, 6, 1, 9, 5, 6, 2, 8};
// 计算数组的大小
int size = sizeof(arr) / sizeof(arr[0]);
// 定义要查找的目标元素
int target = 6;
// 输出原始数组
printf("原始数组: ");
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
// 调用顺序查找函数，返回首次出现的元素的索引
int result = sequentialSearch(arr, size, target);
// 根据查找结果输出相应的信息
if (result != -1)
{
printf("元素 %d 找到，首次出现的索引为 %d\n", target, result);
}
else
{
printf("元素 %d 未找到\n", target);
}
return 0;
}输出结果如下所示：
1.3 时间和空间复杂度分析
// 顺序查找函数，返回首次出现的元素的索引
int sequentialSearch(const int arr[], int size, const int target)
{
for (int i = 0; i < size; ++i)
{
if (arr[i] == target)
{
return i; // 找到目标，返回当前元素的索引
}
}
return -1; // 未找到目标，返回标识
}时间复杂度：
- 最佳情况：如果目标值正好位于列表的第一个位置，则只需要进行一次比较，此时时间复杂度为 O(1)。
- 最坏情况：如果目标值位于列表的最后一个位置，或者列表中根本不存在目标值，那么就需要遍历整个列表，进行 n 次比较，这里 n 是列表中的元素数量，因此最坏情况下的时间复杂度为 O(n)。
- 平均情况：平均情况下，顺序查找的时间复杂度也是 O(n)。这是因为，在平均情况下，我们期望在列表的大约中间位置找到目标值，但这仍然是线性级别的复杂度。
提示：
当我们谈论时间复杂度时，通常指的是平均情况下的时间复杂度。
空间复杂度：
- 顺序查找的空间复杂度为 O(1)。这是因为顺序查找不需要额外的存储空间来完成操作，除了可能用于存储索引或计数器的几个变量之外，这些变量占用的空间是固定的，不会随着输入数据规模的增加而增加。
1.4 适用场景
- 小型数据集：顺序查找适用于小型数据集，因为其时间和空间复杂度较低。
- 未排序的数据集：顺序查找不要求数据集是有序的，因此适用于未排序的数据集。
- 简单实现：顺序查找的实现简单，易于理解和维护，适合初学者学习。
2 二分查找
2.1 算法原理
二分查找（Binary Search）是一种高效的搜索算法，通常用于有序数据集中查找目标元素。其核心思想是通过将数据集划分为两半并与目标进行比较，逐步缩小搜索范围，直到找到目标元素或确定目标不存在。
1. 选择中间元素：在有序数据集中，选择数组的中间元素。
2. 比较目标：将中间元素与目标元素进行比较。
3. 查找成功：如果中间元素等于目标元素，则查找成功，返回中间元素的索引。
4. 缩小搜索范围：
- 对于一个升序的数据集，如果中间元素大于目标元素，说明目标可能在左半部分；如果中间元素小于目标元素，说明目标可能在右半部分。
- 根据比较结果，将搜索范围缩小到一半，继续查找。
5. 重复步骤：重复上述步骤，不断将搜索范围缩小，直到找到目标元素或搜索范围为空。
2.2 算法实现
2.2.1 循环实现
#include <stdio.h>
// 二分查找函数
int binarySearch(const int arr[], int size, const int target)
{
int left = 0; // 初始化左边界
int right = size - 1; // 初始化右边界
while (left <= right)
{
// 计算中间索引
// int mid = (left + right) / 2; // 可能导致的整数溢出
int mid = left + (right - left) / 2;
// 如果中间元素等于目标元素，返回中间元素的索引
if (arr[mid] == target)
{
return mid;
}
// 如果中间元素大于目标元素，在左半部分继续查找
if (arr[mid] > target)
{
right = mid - 1;
}
// 如果中间元素小于目标元素，在右半部分继续查找
else
{
left = mid + 1;
}
}
return -1; // 未找到目标元素，返回标识
}
int main()
{
// 定义一个示例有序数组
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
// 计算数组的大小
int size = sizeof(arr) / sizeof(arr[0]);
// 定义要查找的目标元素
int target = 9;
// 输出有序数组
printf("有序数组: ");
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
// 调用二分查找函数
int result = binarySearch(arr, size, target);
// 根据查找结果输出相应的信息
if (result != -1)
{
printf("元素 %d 找到，索引为 %d\n", target, result);
}
else
{
printf("元素 %d 未找到\n", target);
}
return 0;
}输出结果如下所示：
2.2.2 防止整数溢出
当 left 和 right 都是非常大的正整数时，它们的和可能会超过整数的最大值（例如，在 32 位系统中，整数的最大值是 2,147,483,647）。如果发生这种情况，left + right 会导致整数溢出，结果会变成一个负数或一个非常小的正数，从而导致错误的中间索引计算。
int mid = (left + right) / 2;
- 这种方法直接计算 left 和 right 的和，然后除以 2。
- 如果 left 和 right 都很大，left + right 可能会超过整数的最大值，导致溢出。
int mid = left + (right - left) / 2;
- 这种方法先计算 right - left，然后再除以 2，最后加上 left。
- 由于 right - left 通常是一个较小的值，不会导致溢出。
- 这样可以确保计算结果始终在合法范围内，避免了整数溢出的问题。
因此，使用 int mid = left + (right - left) / 2; 是一种更安全的方法，可以有效防止整数溢出问题。
2.2.3 递归实现
#include <stdio.h>
// 递归二分查找函数
int binarySearchRecursive(const int arr[], int left, int right, int target)
{
// 基本情况：如果左边界大于右边界，表示目标值不在数组中
if (right >= left)
{
// 计算中间索引，防止 (left + right) 可能导致的整数溢出
int mid = left + (right - left) / 2;
// 如果中间元素等于目标元素，返回中间元素的索引
if (arr[mid] == target)
{
return mid;
}
// 如果中间元素大于目标元素，在左半部分继续查找
if (arr[mid] > target)
{
return binarySearchRecursive(arr, left, mid - 1, target);
}
// 如果中间元素小于目标元素，在右半部分继续查找
return binarySearchRecursive(arr, mid + 1, right, target);
}
// 未找到目标元素，返回 -1
return -1;
}
int main()
{
// 定义一个示例有序数组
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
// 计算数组的大小
int size = sizeof(arr) / sizeof(arr[0]);
// 定义要查找的目标元素
int target = 11;
// 输出有序数组
printf("有序数组: ");
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
// 调用递归二分查找函数
int result = binarySearchRecursive(arr, 0, size - 1, target);
// 根据查找结果输出相应的信息
if (result != -1)
{
printf("元素 %d 找到，索引为 %d\n", target, result);
}
else
{
printf("元素 %d 未找到\n", target);
}
return 0;
}输出结果如下所示：
2.3 时间和空间复杂度分析
2.3.1 循环实现的二分查找
时间复杂度：
- 最佳情况：如果目标值正好位于数组的中间位置，只需要进行一次比较，时间复杂度为 O(1)。
- 最坏情况：如果目标值位于数组的最左边或最右边，或者数组中根本不存在目标值，那么需要进行 log2(n) 次比较，其中 n 是数组的长度。因此，最坏情况下的时间复杂度为 O(log n)。
- 平均情况：在平均情况下，二分查找的时间复杂度也是 O(log n)。这是因为每次查找都会将搜索范围减半，直到找到目标值或确定目标值不存在。
空间复杂度：
- 二分查找的空间复杂度为 O(1)。因为二分查找算法只使用了常数级别的额外空间来存储索引变量（left、right、mid）和其他辅助变量。这些变量占用的空间是固定的，不会随着输入数据规模的增加而增加。
2.3.2 递归实现的二分查找
时间复杂度：
- 最佳情况：如果目标值正好位于数组的中间位置，只需要进行一次比较，时间复杂度为 O(1)。
- 最坏情况：如果目标值位于数组的最左边或最右边，或者数组中根本不存在目标值，那么需要进行 log2(n) 次比较，其中 n 是数组的长度。因此，最坏情况下的时间复杂度为 O(log n)。
- 平均情况：在平均情况下，递归二分查找的时间复杂度也是 O(log n)。这是因为每次递归调用都会将搜索范围减半，直到找到目标值或确定目标值不存在。
空间复杂度：
- 递归实现的二分查找的空间复杂度主要由递归调用栈的深度决定。在最坏情况下，递归调用的深度为 log2(n)。每次递归调用都会在调用栈中占用一定的空间来保存当前的参数和局部变量。因此，递归二分查找的空间复杂度为 O(log n)。
| 实现方式 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 循环实现 | O(log n) | O(1) |
| 递归实现 | O(log n) | O(log n) |
2.4 适用场景
- 有序数据集：二分查找要求数据集是有序的，通常用于升序或降序排列的数组。
- 大规模数据集：由于其高效的查找速度，二分查找特别适合用于大规模数据集。
- 静态数据集：如果数据集不经常变化，二分查找可以显著提高查找效率。
原文地址：https://blog.csdn.net/qq_53139964/article/details/143025438
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！