一锅汤资源网站建设大全,佛山cms建站,定制做网站服务,net网站建设语言文章目录 1.线性查找2.二分查找2.1一般的二分查找2.2特殊的二分查找——红绿标记法2.3 原理解释#xff1a;2.4 代码中的应用#xff1a; 1.线性查找
线性查找#xff08;Linear Search#xff09;是一种简单直观的搜索算法#xff0c;用于在数组中查找特定值的位置。它的… 文章目录 1.线性查找2.二分查找2.1一般的二分查找2.2特殊的二分查找——红绿标记法2.3 原理解释2.4 代码中的应用 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); // 输出应该是 2return 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)非常高效地找到符合条件的索引。
