二分查找 递归 非递归

二分查找是一种在有序数组中查找特定元素的常用算法。它的基本思想是通过将数组分成两部分，判断目标元素可能在哪一部分，然后继续在该部分中进行查找，直到找到目标元素或者确定目标元素不存在。

递归实现二分查找的方式是将问题分解为子问题，并通过递归调用来解决子问题。具体步骤如下：
1. 确定数组的左边界和右边界，初始时左边界为0，右边界为数组长度减1。
2. 计算中间元素的索引，即 (左边界 + 右边界) / 2。
3. 比较中间元素与目标元素的大小关系：
- 如果中间元素等于目标元素，则返回中间元素的索引；
- 如果中间元素大于目标元素，则在左半部分继续递归查找；
- 如果中间元素小于目标元素，则在右半部分继续递归查找。
4. 重复步骤2和步骤3，直到找到目标元素或者确定不存在。

非递归实现二分查找的方式是使用循环来迭代地进行查找。具体步骤如下：
1. 确定数组的左边界和右边界，初始时左边界为0，右边界为数组长度减1。
2. 使用循环来迭代查找，直到左边界大于右边界：
- 计算中间元素的索引，即 (左边界 + 右边界) / 2。
- 比较中间元素与目标元素的大小关系：
- 如果中间元素等于目标元素，则返回中间元素的索引；
- 如果中间元素大于目标元素，则将右边界更新为中间元素的索引减1；
- 如果中间元素小于目标元素，则将左边界更新为中间元素的索引加1。
3. 如果循环结束时仍未找到目标元素，则表示目标元素不存在。

递归和非递归两种实现方式都可以实现二分查找，选择哪种方式取决于个人偏好和实际需求。

相关问题

二分查找递归与非递归

二分查找是一种查找算法，可以在有序序列中快速地找到目标元素的位置。它的递归和非递归实现方式如下：

递归实现：

public static int binSearchRecursion(int[] arr, int left, int right, int des) {
    if (arr == null || arr.length < 1) {
        return -1;
    }
    if (left <= right) {
        int mid = left + (right - left) / 2;
        if (des == arr[mid]) {
            return mid;
        } else if (des < arr[mid]) {
            return binSearchRecursion(arr, left, mid - 1, des);
        } else {
            return binSearchRecursion(arr, mid + 1, right, des);
        }
    }
    return -1;
}

非递归实现：

public static int binSearch(int[] arr, int des) {
    if (arr == null || arr.length < 1) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (des == arr[mid]) {
            return mid;
        } else if (des < arr[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

二分查找递归和非递归解读

二分查找是一种常用的查找算法，可以在有序的数组中快速查找目标元素，其时间复杂度为 O(log n)。在实现二分查找时，可以采用递归或非递归的方式。

递归实现二分查找的过程：

1. 如果 low > high，则表示查找失败，返回 -1。
2. 如果 low <= high，则计算 mid = low + (high - low) / 2，即中间位置的下标。
3. 如果 arr[mid] 等于目标元素 target，则直接返回 mid。
4. 如果 arr[mid] 大于目标元素 target，则在前半部分继续查找，即递归调用 binarySearch(arr, low, mid - 1, target)。
5. 如果 arr[mid] 小于目标元素 target，则在后半部分继续查找，即递归调用 binarySearch(arr, mid + 1, high, target)。

非递归实现二分查找的过程：

1. 如果 low > high，则表示查找失败，返回 -1。
2. 如果 low <= high，则计算 mid = low + (high - low) / 2，即中间位置的下标。
3. 如果 arr[mid] 等于目标元素 target，则直接返回 mid。
4. 如果 arr[mid] 大于目标元素 target，则在前半部分继续查找，即将 high 更新为 mid - 1。
5. 如果 arr[mid] 小于目标元素 target，则在后半部分继续查找，即将 low 更新为 mid + 1。
6. 重复步骤 1~5，直到找到目标元素或查找失败。

递归和非递归实现的二分查找算法本质上是一样的，只是实现方式不同。相对而言，递归实现简单易懂，但由于递归调用可能会产生大量的函数调用开销，因此在处理大规模数据时，非递归实现更为高效。