编程实现折半查找算法。
时间: 2023-09-17 07:10:17 浏览: 54
好的,以下是Python语言实现的折半查找算法:
```python
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,`arr`为有序数组,`target`为要查找的目标值。首先将左右边界分别指向数组的开头和结尾,然后不断折半缩小查找范围,直到找到目标值或者查找范围为空。若找到目标值,则返回其在数组中的下标,否则返回-1表示未找到。
相关问题
c语言编程实现折半查找算法
折半查找算法(又称二分查找)是一种针对有序数组的查找算法,它的基本思想是将数组分成两部分,判断要查找的元素在哪一部分中,然后再对该部分进行查找,不断重复这个过程直到找到要查找的元素或者确定该元素不存在为止。
下面给出一个 C 语言编写的折半查找算法的示例代码:
```c
#include <stdio.h>
int binary_search(int arr[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 4, 6, 8, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 6;
int index = binary_search(arr, n, x);
if (index != -1) {
printf("The index of %d is %d\n", x, index);
} else {
printf("%d is not in the array.\n", x);
}
return 0;
}
```
在上面的代码中,`binary_search` 函数用来执行折半查找操作,它的参数 `arr` 是一个有序的整数数组,`n` 是数组的长度,`x` 是要查找的元素。函数的返回值是要查找元素在数组中的索引,如果元素不存在则返回 `-1`。
在 `binary_search` 函数中,首先初始化左右边界,然后在循环中不断缩小查找范围,直到找到要查找的元素或者确定该元素不存在为止。在每次循环中,都计算出当前查找范围的中间位置 `mid`,然后将要查找的元素与中间位置的元素进行比较,如果相等则返回 `mid`,如果要查找的元素比中间位置的元素小,则缩小右边界,否则缩小左边界。
最后在 `main` 函数中,定义了一个有序的整数数组 `arr`,将要查找的元素 `x` 设置为 `6`,然后调用 `binary_search` 函数进行查找,最终输出查找结果。
运行上面的代码,输出结果如下:
```
The index of 6 is 3
```
这表示要查找的元素 `6` 在数组中的索引为 `3`。
用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。最终,根据返回值判断是否查找成功并输出结果。