请给出C语言的折半查找法代码
时间: 2024-02-25 13:57:17 浏览: 26
折半查找法(Binary Search)是一种常用的查找算法,适用于有序数组。其基本思想是:在有序数组中,取中间位置的元素与查找值比较,如果中间位置元素等于查找值,则查找成功;如果中间位置元素大于查找值,则在数组的左半部分继续查找;如果中间位置元素小于查找值,则在数组的右半部分继续查找,直到查找成功或查找结束。
下面是C语言的折半查找法代码实现:
```c
int binarySearch(int a[], int n, int key)
{
int low = 0, high = n-1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1; // 查找失败
}
```
其中,a[]表示有序数组,n表示数组长度,key表示要查找的关键字。如果查找成功,返回该关键字在数组中的下标;如果查找失败,返回-1。
相关问题
C语言顺序查找法和折半查找法代码实现
以下是C语言实现顺序查找和折半查找的代码实现:
1. 顺序查找
```c
#include <stdio.h>
int SeqSearch(int r[], int n, int k) {
r[0] = k; // 下标0用作哨兵存放待查找的元素
int i;
for (i = n; r[i] != k; i--); // 从后往前查找
return i; // 返回查找到的元素下标,未找到返回0
}
int main() {
int r[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(r) / sizeof(int) - 1; // 数组长度
int k = 5; // 待查找元素
int index = SeqSearch(r, n, k);
if (index) {
printf("找到元素%d了,在第%d个\n", k, index);
} else {
printf("找不到该元素%d\n", k);
}
return 0;
}
```
2. 折半查找
```c
#include <stdio.h>
int BinSearch(int r[], int n, int k) {
int low = 1, high = n, mid;
while (low <= high) {
mid = (low + high) / 2;
if (r[mid] == k) {
return mid;
} else if (r[mid] > k) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return 0; // 未找到返回0
}
int main() {
int r[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(r) / sizeof(int) - 1; // 数组长度
int k = 5; // 待查找元素
int index = BinSearch(r, n, k);
if (index) {
printf("找到元素%d了,在第%d个\n", k, index);
} else {
printf("找不到该元素%d\n", k);
}
return 0;
}
```
c语言折半查找法找字符,C语言简单实现折半查找法
折半查找法(Binary Search)是一种基于比较目标值和数组中间元素的查找算法。它的时间复杂度为O(log n)。
以下是在一个已排序的字符数组中使用C语言实现折半查找法的示例代码:
```c
#include <stdio.h>
int binarySearch(char arr[], int left, int right, char target) {
if (right >= left) {
int mid = left + (right - left) / 2;
// 如果目标字符位于中间位置,则返回中间位置的下标
if (arr[mid] == target)
return mid;
// 如果目标字符比中间字符小,则在左半部分继续查找
if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target);
// 否则,在右半部分继续查找
return binarySearch(arr, mid + 1, right, target);
}
// 如果未找到目标字符,则返回-1
return -1;
}
int main() {
char arr[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
int n = sizeof(arr) / sizeof(arr[0]);
char target = 'd';
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1)
printf("未找到目标字符\n");
else
printf("目标字符位于下标 %d\n", result);
return 0;
}
```
该程序输出结果为:
```
目标字符位于下标 3
```
注意:在使用折半查找法前,必须先将待查找的字符数组按照升序或者降序排列。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)