折半查找算法c#代码
时间: 2024-06-02 07:05:44 浏览: 22
折半查找算法,也叫二分查找算法,是一种高效的查找算法。它的基本思想是将有序数组分成两部分,取中间值与待查找值进行比较,如果中间值大于待查找值,则在左边继续查找;如果中间值小于待查找值,则在右边继续查找,直到找到待查找值或者查找完整个数组。以下是C#代码实现:
```
public static int BinarySearch(int[] arr, int key)
{
int left = 0, right = arr.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == key)
{
return mid;
}
else if (arr[mid] > key)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1; //未找到
}
```
相关问题
数据结构折半查找算法和完整代码
折半查找算法,也称为二分查找算法,是一种在有序数组中查找特定元素的算法。它通过将目标值与数组中间元素进行比较,并根据比较结果缩小查找范围,直到找到目标值或查找范围为空为止。
以下是使用C语言编写的折半查找算法的完整代码示例:
```c
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid; // 目标值找到,返回索引
} else if (arr[mid] < target) {
low = mid + 1; // 目标值在右侧,缩小查找范围
} else {
high = mid - 1; // 目标值在左侧,缩小查找范围
}
}
return -1; // 目标值不存在,返回-1
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 9;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1) {
printf("目标值 %d 不存在\n", target);
} else {
printf("目标值 %d 的索引是 %d\n", target, result);
}
return 0;
}
```
在上述代码中,`binarySearch`函数接受一个有序数组`arr`、查找范围的下界`low`、上界`high`和目标值`target`作为参数。它使用一个`while`循环来不断缩小查找范围,直到找到目标值或查找范围为空为止。如果目标值存在,则返回其索引;否则,返回-1。
在`main`函数中,我们定义了一个有序数组`arr`,并计算出其元素个数。然后,我们调用`binarySearch`函数来查找目标值9,并根据返回结果输出相应的信息。
运行上述代码,输出结果为:
```
目标值 9 的索引是 4
```
这表明目标值9在数组中的索引为4。
数据结构折半查找算法
折半查找算法,也称为二分查找算法,是一种在有序数组中查找给定值的高效算法。
算法步骤如下:
1. 初始化左指针 low 为数组起始位置,右指针 high 为数组末尾位置。
2. 计算中间位置 mid = (low + high) / 2。
3. 比较数组中间元素与目标值的大小:
- 若中间元素等于目标值,则返回查找成功。
- 若中间元素大于目标值,则将 high 更新为 mid - 1,继续在左半部分查找。
- 若中间元素小于目标值,则将 low 更新为 mid + 1,继续在右半部分查找。
4. 重复步骤2和步骤3,直到 low 大于 high,表示查找失败。
折半查找算法的时间复杂度为 O(log n),其中 n 是数组的长度。它是一种效率较高的查找算法,但要求待查找的数组必须是有序的。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)