JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)

简介: JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)

前言

查找算法中,首要讨论的是基本查找,也就是顺序查找,在数据量特别大的时候,基本查找这种从前往后挨个找的形式,性能是很差的!


所以为了提高一些性能,产生了各种查找算法。这里要学习介绍的是二分查找,也叫折半查找。


二分查找有一个前提条件和一个核心思想:


  • 前提条件:数组中的数据必须是有序的
  • 核心思想:每次排除一半的数据,查询数据的性能明显提高许多!

假设有一个有序数组, { 7,2,79,81,103,127,131,147}

我们用图解来推演一下是如何进行查找的:

详细图解

以查找131为例:

(此处的right 坐左朝右;left 坐右朝左。不要模仿doge)

注意:二分查找正常的折半条件应该是开始位置let<=结束位置right!

代码部分

package user.Arithmetic;
 
public class BinarySearch {
    public static void main(String[] args) {
        //1.准好好一个数组
        int[] arr = { 7,2,79,81,103,127,131,147};
        System.out.println(myBinarySearch(arr,131));
    }
    public static int myBinarySearch(int[] arr,int data){
        //1.定义两个变量,一个在初始位置,另一个在末尾位置
        int left = 0;
        int right = arr.length - 1;
 
        //2.定义一个循环控制折半
        while(left <= right){
            //3.每次折半,都要算出中间位置处的索引
            int middle = (left + right) / 2;
            //4.判断当前要找的元素值,与中间位置处的元素值的大小
            if(data < arr[middle]){
                //往左边找,右边的索引改为: 中间索引 - 1
                right = middle - 1;
            }else if(data > arr[middle]){
                //往右边找,左边的索引改为: 中间索引 + 1
                left = middle + 1;
            }else{
                //中间位置处的元素值,正好等于我们要找的元素值
                return middle;
            }
        }
        return -1;
    }
}

运行结果:


END



目录
相关文章
|
15天前
|
算法 索引
【算法】——二分查找合集
二分查找基础模版和进阶模版,查找元素位置,搜索插入位置,x的平方根,山脉数组的峰顶索引,寻找峰值,点名
|
1月前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
71 1
|
2月前
|
存储 缓存 算法
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
|
2月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
2月前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
55 3
|
2月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
3月前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
3月前
|
搜索推荐
插入排序算法的讲解和代码
【10月更文挑战第12天】插入排序是一种基础的排序算法,理解和掌握它对于学习其他排序算法以及数据结构都具有重要意义。你可以通过实际操作和分析,进一步深入了解插入排序的特点和应用场景,以便在实际编程中更好地运用它。
|
3月前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法