• 技术文章 >Java >java教程

    图解Java经典算法折半查找的原理与实现

    WBOYWBOY2022-09-14 19:43:45转载183
    本篇文章给大家带来了关于java的相关知识,折半查找法也叫做⼆分查找,顾名思义就是把数据分成两半,再判断所查找的key在哪⼀半中,再重复上述步骤知道找到⽬标key,下面一起来看一下,希望对大家有帮助。

    php入门到就业线上直播课:进入学习

    推荐学习:《java视频教程

    二分查找

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法,可以在数据规模的对数时间复杂度内完成查找。是一种在有序数组中查找某一特定元素的搜索算法。

    算法思路

    以升序数列为例,比较目标元素与数列中间位置的元素的大小,如果目标元素比中间位置的元素大,则继续在数列的后半部分中进行二分查找;如果目标元素比中间位置的元素小,则在数列的前半部分进行比较;如果相等,则找到了元素的位置。每次比较的数列长度都会是之前数列的一半,直到找到相等元素的位置或者最终没有找到目标元素。

    图解

    给定一个有序的升序排列的数组 nums=[-1,0,2,5,8,12,18,38,43,46]

    然后在该数组中找到目标值 target = 12。

    图解如下:

    力扣原题

    传送门

    题目描述:

    给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

    示例 1:

    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4

    示例 2:

    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

    解题思路:

    根据题意得出该数组为有序数组,这也是使用二分查找的前提条件。

    Java代码实现:

    class Solution {
        public int search(int[] nums, int target) {
            int left = 0,right = nums.length - 1;
            while(left <= right) { // 循环条件
                int mid = left + (right - left) / 2;
                if(nums[mid] == target){
                    return mid;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return -1;  // 找不到则返回-1
        }
    }

    复杂度分析:

    推荐学习:《java视频教程

    以上就是图解Java经典算法折半查找的原理与实现的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:脚本之家,如有侵犯,请联系admin@php.cn删除
    专题推荐:java
    上一篇:总结分享Java比较两个对象大小的三种方法 下一篇:【整理分享】8种开发工具,提升工作效率,再也不做加班人!
    VIP课程(WEB全栈开发)

    相关文章推荐

    • ❤️‍🔥共22门课程,总价3725元,会员免费学• 一起聊聊Java Valhalla Project项目• java是值传递还是引用传递• jquery框架是java的吗• 关于JavaScript中的数组方法和循环• 总结分享Java比较两个对象大小的三种方法
    1/1

    PHP中文网