1.线性查找
线性查找(Linear Search)是一种简单直观的搜索算法,用于在数组中查找特定值的位置。它的基本思想是逐个检查数组中的每个元素,直到找到目标元素或者遍历完整个数组。
下面是线性查找的基本实现步骤:
- 遍历数组:从数组的第一个元素开始,逐个检查每个元素。
- 比较目标值:将当前元素与目标值进行比较。
- 找到目标:如果找到目标值,返回当前元素的索引。
- 未找到目标:如果遍历完整个数组都没有找到目标值,返回一个指定的表示未找到的值(例如
-1
)。
下面是一个简单的 C 语言实现示例,展示了如何使用线性查找在数组中查找特定的目标值:
#include <stdio.h>
// 线性查找函数,返回目标值在数组中的索引,如果找不到则返回 -1
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // 找到目标值,返回索引 i
}
}
return -1; // 没有找到目标值,返回 -1
}
int main() {
int arr[] = {23, 4, 16, 42, 8, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 42;
int result = linearSearch(arr, n, target);
if (result != -1) {
printf("目标值 %d 找到在数组中的索引为 %d\n", target, result);
} else {
printf("目标值 %d 在数组中未找到\n", target);
}
return 0;
}
解释代码细节:
linearSearch
函数接受三个参数:arr
(待查找的数组),n
(数组的大小),target
(要查找的目标值)。- 函数使用
for
循环遍历数组arr
中的每个元素。 - 在循环体中,使用
if
条件语句检查当前元素arr[i]
是否等于目标值target
。 - 如果找到目标值,则立即返回当前元素的索引
i
。 - 如果遍历完整个数组都没有找到目标值,则返回
-1
表示未找到。
2.二分查找
2.1一般的二分查找
二分查找(Binary Search)是一种高效的搜索算法,适用于已经排好序的数组。它的基本思想是通过将目标值与数组中间元素进行比较,从而排除一半的数据,从而快速缩小搜索范围。
二分查找的步骤:
- 初始化:确定数组的左右边界,通常左边界为
left = 0
,右边界为right = n - 1
,其中n
是数组的长度。 - 循环条件:只要
left
小于等于right
,就继续查找。 - 中间元素:计算中间元素的索引
mid
,一般为mid = (left + right) / 2
。 - 比较目标值:
- 如果目标值等于
arr[mid]
,则找到目标,返回mid
。 - 如果目标值小于
arr[mid]
,则在左半部分继续查找,更新right = mid - 1
。 - 如果目标值大于
arr[mid]
,则在右半部分继续查找,更新left = mid + 1
。
- 如果目标值等于
- 未找到目标:如果循环结束时仍未找到目标值,则表示数组中不存在该值,返回
-1
或者其他指定的未找到标志。
2.2特殊的二分查找——红绿标记法
但是,在这里,我打算介绍一种新型的二分查找方法——红绿标记法
#include <stdio.h>
// 函数声明
int findMinGreenIndex(int nums[], int n, int target);
int isGreen(int num, int target);
// 寻找第一个大于等于 target 的元素的索引
int findMinGreenIndex(int nums[], int n, int target) {
int red = -1;
int green = n;
int mid = 0;
while (red + 1 < green) {
mid = (red + green) / 2;
if (isGreen(nums[mid], target)) {
green = mid;
} else {
red = mid;
}
}
return green;
}
// 判断是否大于等于 target
int isGreen(int num, int target) {
return num >= target;
}
int main(void) {
int nums[5] = {1, 2, 3, 4, 5};
int number = findMinGreenIndex(nums, 5, 3);
printf("%d\n", number); // 输出应该是 2
return 0;
}
2.3 原理解释:
定义变量:
red
:初始为-1,表示小于目标值的范围的右边界。green
:初始为n,表示大于等于目标值的范围的左边界。mid
:中间位置的索引。
循环条件:
- 当
red + 1 < green
时,表示范围内还有元素未处理。
- 当
计算中间位置
mid
:mid = (red + green) / 2
,计算中间索引位置。
判断条件:
- 调用
isGreen(nums[mid], target)
函数,判断nums[mid]
是否大于等于target
。 - 如果是,则将
green
缩小到mid
,因为我们要找的是第一个大于等于target
的元素,可能还有更小的索引满足条件,所以缩小搜索范围到左侧。 - 如果不是,则将
red
扩展到mid
,因为nums[mid]
小于target
,所以将搜索范围缩小到右侧。
- 调用
返回结果:
- 当循环结束时,返回
green
,即找到的第一个大于等于target
的元素的索引。
- 当循环结束时,返回
2.4 代码中的应用:
- 在
main
函数中,数组nums
中有序地存储了{1, 2, 3, 4, 5}
。 - 调用
findMinGreenIndex(nums, 5, 3)
,期望找到大于等于3
的第一个元素的索引。 - 在这个例子中,
3
在数组中的索引为2
,因此输出结果应为2
。
这种红绿标记法的优点在于,它通过修改搜索范围的两个边界red
和green
,在每次迭代中都将搜索范围缩小一半,因此时间复杂度为O(log n)
,非常高效地找到符合条件的索引。