二分查找(递归)
发布日期:2021-05-07 22:03:35 浏览次数:11 分类:精选文章

本文共 1077 字,大约阅读时间需要 3 分钟。

为了解决这个问题,我们需要找到一个排好序的整型数组中比给定数字稍微大一点的那个位置。如果没有找到这样的位置,则返回-1。我们将使用二分查找来高效地解决这个问题。

方法思路

  • 问题分析:由于数组是排好序的,二分查找是一个高效的选择。我们需要找到第一个大于给定数字的位置。
  • 递归设计:递归方法需要传入数组、起始位置、结束位置和目标数字。中间位置的计算是关键,根据目标数字的大小决定搜索方向。
  • 终止条件:当起始位置和结束位置相邻时,比较目标数字和当前位置的值,决定返回起始位置还是结束位置。
  • 解决代码

    public class Main {    public static void main(String[] args) {        int arr[] = {1, 5, 11, 24, 25, 32, 32, 32, 33};        System.out.println(solve(arr, 32));    }    public static int solve(int arr[], int x) {        if (x >= arr[arr.length - 1])            return -1;        return solve(arr, 0, arr.length - 1, x);    }    private static int solve(int[] arr, int begin, int end, int x) {        if (end - begin == 1) {            if (arr[begin] > x)                return begin;            return end;        }        int k = (begin + end) / 2;        if (x >= arr[k])            return solve(arr, k, end, x);        return solve(arr, begin, k, x);    }}

    代码解释

  • 主函数:调用solve方法,传入数组和目标数字。
  • 初始检查:如果目标数字大于或等于数组的最大值,直接返回-1。
  • 递归方法:计算中间位置,根据目标数字的大小决定搜索方向。终止条件是起始位置和结束位置相邻,比较目标数字和当前位置的值,返回合适的位置。
  • 这个方法利用了二分查找的高效性,确保在O(log n)时间复杂度内找到目标位置。

    上一篇:猜字母
    下一篇:深度优先搜索之代表团出访

    发表评论

    最新留言

    不错!
    [***.144.177.141]2025年04月11日 03时55分10秒