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



目录
相关文章
|
4天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
11天前
|
算法 PHP
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
9 1
|
18天前
|
存储 算法 C语言
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现
|
22天前
|
机器学习/深度学习 算法 索引
数据结构算法--1 顺序查找二分查找
**顺序查找时间复杂度为O(n)**,适合无序列表,可以通过`enumerate`或直接遍历索引来实现。**二分查找时间复杂度为O(logn)**,适用于有序列表,利用Python中`left`、`right`指针和`mid`点不断缩小搜索范围。效率上二分查找更优。
|
22天前
|
存储 算法 Java
Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。
【6月更文挑战第21天】Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。简单哈希表实现未涵盖冲突解决和删除操作。
19 1
|
7天前
|
算法 JavaScript
JS 【算法】二分查找
JS 【算法】二分查找
9 0
|
18天前
|
人工智能 算法 Java
java中经典算法代码整理
java中经典算法代码整理
20 0
|
19天前
|
算法
算法入门——二分查找
算法入门——二分查找
12 0
|
19天前
|
算法 IDE 开发工具
c语言的经典算法代码
c语言进阶11-经典算法代码