二分查找的设计思想或相应的函数代码
时间: 2023-12-09 22:03:50 浏览: 80
二分查找的设计思想是基于分治的思想,每次将查找区间一分为二,然后根据目标值与中间值的比较结果,确定接下来需要查找的区间。该算法的时间复杂度为 O(log n),其中 n 是数组的长度。
以下是一个示例二分查找函数的代码实现:
```python
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
该函数接受一个有序数组 nums 和一个目标值 target,返回目标值在数组中的下标,如果目标值不在数组中,则返回 -1。函数采用了循环的方式实现二分查找,通过不断调整左右边界来缩小查找区间。具体实现中,先将左右边界初始化为数组的首尾下标,然后在循环中计算中间值 mid,根据目标值与中间值的大小关系来更新左右边界,直到找到目标值或者查找区间为空。
相关问题
请写出二分查找的设计思想或相应的函数代码
二分查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两部分,通过比较中间元素和目标元素的大小关系,确定下一步查找的方向,直到找到目标元素或确定不存在该元素为止。
二分查找的时间复杂度为 O(log n),是一种高效的查找算法。
以下是二分查找的函数代码实现:
```
int binarySearch(int arr[], int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, left, mid - 1, x);
return binarySearch(arr, mid + 1, right, x);
}
return -1;
}
```
其中,arr 表示要查找的有序数组,left 和 right 分别表示数组的左右边界,x 表示要查找的元素。首先判断 right 是否大于等于 left,若成立,则求出中间位置 mid,如果 arr[mid] 等于 x,则找到了目标元素,返回 mid;如果 arr[mid] 大于 x,则在左半部分继续查找,即递归调用函数 binarySearch(arr, left, mid - 1, x);如果 arr[mid] 小于 x,则在右半部分继续查找,即递归调用函数 binarySearch(arr, mid + 1, right, x)。若最终未查找到目标元素,则返回 -1。
递归算法实现二分查找
递归算法实现二分查找是一种基于分治思想的算法。通过将数组不断地分成两半,然后在其中一半中查找目标值,再根据查找结果决定继续在左半部分还是右半部分进行查找,直到找到目标值或者确定目标值不存在为止。下面是一个使用C语言实现递归算法实现二分查找的示例代码:
```c
#include <stdio.h>
int binarySearch(int arr[], int min, int max, int key) {
if (min <= max) {
int mid = (min + max) / 2;
if (key == arr[mid]) {
return mid;
}
else if (key < arr[mid]) {
return binarySearch(arr, min, mid - 1, key);
}
else {
return binarySearch(arr, mid + 1, max, key);
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 10, 13, 14, 17, 22, 33, 56, 78};
int len = sizeof(arr) / sizeof(int); int key = 33;
int result = binarySearch(arr, 0, len - 1, key);
if (result == -1) {
printf("目标值 %d 不存在于数组中\n", key);
}
else {
printf("目标值 %d 的下标是:%d\n", key, result);
}
return 0;
}
```
在这个示例代码中,我们定义了一个名为`binarySearch`的递归函数,它接受一个有序数组`arr`、最左边的边界`min`、最右边的边界`max`和目标值`key`作为参数。函数首先计算数组中间值的下标`mid`,然后与目标值进行比较。如果相等,则返回下标`mid`;如果目标值小于中间值,则继续在左半部分进行递归查找;如果目标值大于中间值,则继续在右半部分进行递归查找。如果最终无法找到目标值,则返回-1。在主函数中,我们定义了一个有序数组`arr`,设置了目标值`key`为33,并调用`binarySearch`函数进行查找。最后根据查找结果输出相应的信息。在这个示例代码中,递归函数实现了二分查找算法,通过不断地分割数组并在其中一半中查找,最终找到了目标值33,并返回了它的下标10。<span class="em">1</span><span class="em">2</span>
#### 引用[.reference_title]
- *1* [Python递归函数 二分查找算法实现解析](https://download.csdn.net/download/weixin_38716590/12860476)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [C语言 递归函数实现二分查找](https://blog.csdn.net/weixin_44272350/article/details/119796743)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.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)