用c语言写一个代码,实现折半查找算法
时间: 2024-01-28 22:02:58 浏览: 27
好的,以下是 C 语言的折半查找算法代码:
```c
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
其中,arr 表示有序数组,n 表示数组长度,target 表示待查找元素。该函数通过不断缩小查找范围,最终找到目标元素或者判断其不存在,返回相应的下标或 -1。
相关问题
使用C语言编程实现折半查找算法
折半查找算法(也称二分查找)是一种用于有序数组的查找算法,它的时间复杂度为O(log n)。下面是使用C语言实现折半查找的代码:
```c
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; //未找到
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 23;
int index = binarySearch(arr, 0, n - 1, key);
if (index == -1) {
printf("未找到");
} else {
printf("元素 %d 的索引为 %d", key, index);
}
return 0;
}
```
在上面的代码中,我们定义了一个 `binarySearch` 函数来实现折半查找。该函数接受四个参数:要查找的有序数组 `arr`,左边界 `left`,右边界 `right` 和要查找的元素 `key`。在函数体内,我们使用 `while` 循环来不断缩小查找范围,直到找到要查找的元素或者查找范围为空。具体实现中,我们首先计算出中间元素的索引 `mid`,然后将其与要查找的元素 `key` 进行比较。如果相等,则返回 `mid`;如果 `arr[mid] < key`,则说明要查找的元素在中间元素的右侧,更新 `left = mid + 1`;如果 `arr[mid] > key`,则说明要查找的元素在中间元素的左侧,更新 `right = mid - 1`。如果未找到要查找的元素,则返回 `-1`。
在上面的代码中,我们还定义了一个 `main` 函数来测试 `binarySearch` 函数。我们首先定义了一个有序数组 `arr`,然后计算出数组的长度 `n`。接下来,我们定义要查找的元素 `key` 为 `23`,并将它传递给 `binarySearch` 函数。最后,我们判断是否找到了要查找的元素,并输出结果。
用C语言编程实现折半查找算法
折半查找算法(Binary Search),也叫二分查找算法,是一种查找有序数组中某个元素的算法。它使用了分治策略来减少需要被查找的元素数量。
具体实现步骤如下:
1. 定义要查找的元素值 key;
2. 定义数组的左右边界,left 和 right,初始值分别为 0 和数组长度减 1;
3. 取中间位置 mid,mid 的值为 (left + right) / 2;
4. 如果 key 等于 mid 位置上的元素,则返回 mid;
5. 如果 key 小于 mid 位置上的元素,则在数组的左半部分进行二分查找,即将 right 改为 mid-1;
6. 如果 key 大于 mid 位置上的元素,则在数组的右半部分进行二分查找,即将 left 改为 mid+1;
7. 如果 left 大于 right,则说明要查找的元素不存在于数组中,返回 -1。
以下是用 C 语言实现折半查找算法的代码:
```c
#include <stdio.h>
int binary_search(int arr[], int n, int key) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (key == arr[mid]) {
return mid;
} else if (key < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 8;
int index = binary_search(arr, n, key);
if (index == -1) {
printf("Element not found\n");
} else {
printf("Element found at index %d\n", index);
}
return 0;
}
```
以上代码中,我们定义了一个 `binary_search` 函数来实现折半查找算法。在 `main` 函数中,我们定义了一个有序数组 `arr`,然后调用 `binary_search` 函数查找元素值为 `key` 的元素在数组中的位置。如果查找成功,函数返回该元素在数组中的下标;否则返回 -1。最终,根据返回值判断是否查找成功并输出结果。