二分查找的设计思想或相应的函数代码

二分查找的设计思想是基于分治的思想，每次将查找区间一分为二，然后根据目标值与中间值的比较结果，确定接下来需要查找的区间。该算法的时间复杂度为 O(log n)，其中 n 是数组的长度。

以下是一个示例二分查找函数的代码实现：

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语言实现递归算法实现二分查找的示例代码：

#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 ]