首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。(递归或者非递归实现)

实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。(递归或者非递归实现)

作者头像
GeekLiHua
发布于 2025-01-21 17:26:45
发布于 2025-01-21 17:26:45
1.1K0
举报
文章被收录于专栏:JavaJava

实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。(递归或者非递归实现)

简介:实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。(递归或者非递归实现)

算法思路

算法思路

二分查找是一种在有序数组中查找特定元素的搜索算法。该算法对数组进行比较次数的上限是 O(log n)。核心思想是通过每次将查找区间缩小一半来逐步接近查找目标。因为每次查找后查找区间都缩小了一半,所以时间复杂度是对数级别。

具体实现如下:

  1. 选择左右两端点取中间值,然后与目标值相比较
  2. 如果当前中间值大于目标值,则说明目标值只可能在mid左侧,所以再次在[l, mid-1]区间进行查找
  3. 如果当前中间值小于目标值,则说明目标值只可能在mid右侧,所以再次在[mid+1, r]区间进行查找
  4. 重复执行步骤1~3,直到找到目标值或确定不存在目标值

下面是C++代码实现,每行注释详细解释其作用:

代码语言:javascript
复制
#include <iostream>
using namespace std;

int binarySearch(int arr[], int l, int r, int x) { // 当前查找区间为 [left, right]
    if (r >= l) { // 当还有剩余未查找的元素时循环
        int mid = l + (r - l) / 2; // 取中间值
        if (arr[mid] == x) return mid; // 如果中间值等于目标值,则直接返回
        if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // 如果中间值大于目标值,则在左边的区间中查找
        return binarySearch(arr, mid + 1, r, x); // 否则在右边的区间中查找
    }
    return -1; // 如果数组中不存在目标元素,则返回-1
}

int main() {
    int arr[] = {1, 3, 5, 7, 9}; // 已排序数组a
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度为n
    int x = 5; // 要查找的元素x
    int result = binarySearch(arr, 0, n - 1, x); // 调用二分搜索函数
    cout << "The index of " << x << " in array is: " << result << endl; // 输出结果
    return 0;
}

需要注意的是,在实现中我们使用递归方式进行查找。每次将当前查找区间中点与目标值进行比较,如果相等,则表示已经找到目标元素;如果中间值大于目标元素,则说明目标元素只可能在mid左侧,所以再次在[l, mid-1]区间进行查找;否则说明目标元素只可能在mid右侧,所以再次在[mid+1, r]区间进行查找。重复执行这个过程,直到找到或确定不存在目标元素。

同时,递归方式的实现还需要注意满足递归退出条件。当当前查找区间[l, r]变成[low, high]时,如果high < low,则说明不存在目标元素,返回-1即可。

  • Java版本
代码语言:javascript
复制
class Solution {

    public int binarySearch(int[] arr, int l, int r, int x) {
        if (r >= l) { // 当还有剩余未查找的元素时循环
            int mid = l + (r - l) / 2; // 取中间值
            if (arr[mid] == x) return mid; // 如果中间值等于目标值,则直接返回
            if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // 如果中间值大于目标值,则在左边的区间中查找
            return binarySearch(arr, mid + 1, r, x); // 否则在右边的区间中查找
        }
        return -1; // 如果数组中不存在目标元素,则返回-1
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {1, 3, 5, 7, 9}; // 已排序数组a
        int n = arr.length; // 数组长度为n
        int x = 5; // 需要查找的目标值
        int result = sol.binarySearch(arr, 0, n - 1, x); // 调用二分搜索函数
        System.out.println("The index of " + x + " in array is: " + result); // 输出结果
    }
}

同样地,在Java中我们也使用递归方式进行查找。每次将当前查找区间中点与目标值进行比较,如果相等,则表示已经找到目标元素;如果中间值大于目标元素,则说明目标元素只可能在mid左侧,所以再次在[l, mid-1]区间进行查找;否则说明目标元素只可能在mid右侧,所以再次在[mid+1, r]区间进行查找。重复执行这个过程,直到找到或确定不存在目标元素。

同时,递归方式的实现还需要注意满足递归退出条件。当当前查找区间[l, r]变成[low, high]时,如果high < low,则说明不存在目标元素,返回-1即可。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-20,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 实现一个二分搜索算法,搜索指定元素在已排序数组中的位置。(递归或者非递归实现)
    • 算法思路
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档