图解Java经典算法折半查找的原理与实现
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
二分查找
二分查找也称折半查找（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
解题思路：
根据题意得出该数组为有序数组，这也是使用二分查找的前提条件。
- 定义两个指针分别指向数组的首尾两个元素；
- 找到数组的中间值mid；
- 如果
nums[mid] < target，则 target 位于数组的后半部分，反之nums[mid] > target在前半部分； - 重复上一步操作，直到
nums[mid] = target，说明找到target，返回下标即可。
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
}
}
复杂度分析：
- 时间复杂度：O(logn)，其中 n 是数组的长度。
- 空间复杂度：O(1)。
到此这篇关于图解Java经典算法折半查找的原理与实现的文章就介绍到这了,更多相关Java折半查找内容请搜索程序员之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持程序员之家！
相关文章
这篇文章主要介绍了java验证码生成的基本流程，需要的朋友可以参考下2015-11-11
License指的是版权许可证，那么对于SpringBoot项目，如何增加License呢？本文就来介绍一下，感兴趣的可以了解一下2021-06-06
这篇文章主要介绍了java常见事件响应方法,对于初学者有很好的参考借鉴价值,分享给大家,需要的朋友可以参考下2014-08-08
这篇文章主要介绍了Maven聚合开发实例代码，本文通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下2023-03-03
这篇文章主要介绍了Spring中的Actuator使用详解,在生产环境中运行的程序,并不总是稳定、安静、正确的,往往会遇到各式各样的现场状况,这个时候,就需要获取该程序足够多的运行状态信息,然后分析并对其进行有效管理,需要的朋友可以参考下2023-09-09
这篇文章主要介绍了JAVA对CSV格式文本数据处理后再保存成新CSV格式文本的模板,可以学习到java读取csv文件和写csv的方法,需要的朋友可以参考下2014-03-03
Cookie又称“小甜饼”，类型为“小型文本文件”，指某些网站为了辨别用户身份而储存在用户本地终端（Client Side）上的数据（通常经过加密）。由用户客户端计算机暂时或永久保存的信息。本文将讲解Cookie在Java中的使用，感兴趣的朋友可以了解下2021-05-05
这篇文章主要介绍了Java中的Map集合简单汇总解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下2019-10-10
Springboot实现邮箱验证码注册与修改密码及登录功能详解流程
验证码作为一种自然人的机器人的判别工具，被广泛的用于各种防止程序做自动化的场景中。传统的字符型验证安全性已经名存实亡的情况下，各种新型的验证码如雨后春笋般涌现，今天给大家分享一篇SpringBoot实现滑块验证码2022-11-11
Springboot jar文件如何打包zip在linux环境运行
这篇文章主要介绍了Springboot jar文件如何打包zip在linux环境运行,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下2020-02-02
最新评论