数据结构 -- 二分查找

本文主要梳理了二分查找算法的几种实现思路,基本概念参考 顺序、二分、哈希查找的区别及联系_生成一个大小为10万的有序数组,随机查找一个元素,分别采用顺序查找和二分查找方式-CSDN博客

1、基本概念

(1)前提条件:待查找数据必须有序。

(2)实现方式:在查找过程中,它先和中间的比较,如果等于就直接返回,如果小于就在前半部分继续使用二分法进行查找,如果大于则在后半部分继续使用二分法进行查找。

2、算法实现

2.1 基本版实现

package com.hh.algorithm.find;

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1,2,4,5,5,6,7,8,9,11,23};
        System.out.println(BinarySearch.binary(arr, 4));
    }
    public static int binary(int[] arr, int key) {
        int i = 0;
        int j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (key < arr[mid]) {
                j = mid - 1;
            } else if (key > arr[mid]) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

}

问题1:为什么是 i<=j ,而不是 i<j?

(1)i==j:意味着 i,j 它们指向的元素也会参与比较;

(2)i<j:只意味着mid 指向的元素参与比较。

问题2:j - ((j - i) >> 1) 与 (i+j)/2都是相加除2,使用后者有没有问题?

当超出 int 的范围时,他会把最高位视为符号位。

代码实现

package com.hh.algorithm.find;

public class BinarySearchTest {

    public static void main(String[] args) {
         /*
        同一个二进制数
        1011 1111 1111 1111 1111 1111 1111 1110

        没有超出int 范围,默认是:不把最高位视为符号位,代表3221225470
        超出int 范围,把最高位视为符号位,代表-1073741826

        所以,当计算结果超出int的范围时,他就会把最高位视为符号位
         */
        int i = 0;
        int j = Integer.MAX_VALUE - 1;

        int mid = (j + i) / 2;
        int mid2 = (i + j) >>> 1;
        System.out.println("第1轮(j + i) / 2:" + mid);
        System.out.println("第1轮(j+i)/2:" + mid2);

        System.out.println("---------------------");
        i = mid+1;
        mid = (j + i) / 2;
        mid2 = (i + j) >>> 1;
        System.out.println("第2轮(j + i) / 2:" + mid);
        System.out.println("第2轮(j+i)/2:" + mid2);
        /*
           扩展:
           (1)(j + i) / 2还有另一种写法,也就是 j - (j - i) / 2
           (2)j - (j - i) / 2 拆开就是 j - j/2 + i/2  --> j/2 + i/2  --> (j + i) / 2
         */
    }
}

运行结果

2.2 平衡版实现

package com.hh.algorithm.find;
/*
            // 如果待查找数字一直在左边,if那么就会判断比较log(n)次
            if (key < arr[mid]) {
                j = mid - 1;
            } else if (key > arr[mid]) {
                // 如果待查找数字一直在右边,if那么就会判断比较2log(n)次
                i = mid + 1;
            } else {
                return mid;
            }
         解决方式:
            1.左闭右开的区间,i指向的可能是目标,而j指向的不是目标
            2.不在循环内找出,等范围内只剩i时,退出循环,在循环外比较 a[i]与target
            3.循环内的平均比较次数减少了
            4.时间复杂度    θ(log(n))
*/
public class BinarySearch2 {

    public static void main(String[] args) {
        int[] arr = {1,2,4,5,5,6,7,8,9,11,23};
        System.out.println(BinarySearch2.binary(arr, 4));
    }

    public static int binary(int[] arr, int key) {
        int i = 0;
        int j = arr.length;
        while (i + 1 < j) {
            int mid = (i + j) >>> 1;
            if (key < arr[mid]) {
                j = mid;
            } else{
                i = mid;
            }
        }
        return (key == arr[i])? i : -1;
    }

}

运行结果

2.3 java版实现

package com.hh.algorithm.find;

/**
 * 下面是java版本的二分查找代码实现,粘贴了底层代码
 */
public class BinarySearch3 {

    public static void main(String[] args) {
        int[] arr = {1,2,4,5,5,6,7,8,9,11,23};
        System.out.println(BinarySearch3.binarySearch(arr,4));
    }
    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        //没找到就返回插入点位置
        return -(low + 1);  // key not found.
    }
}

运行结果

2.4 有重复元素的数组,返回左右

package com.hh.algorithm.find;

/**
 * 当该数组有重复元素时,返回最靠左(右)的元素位置
 */
public class BinarySearchMost {

    public static void main(String[] args) {
        int[] arr = {1,2,4,5,7,7,7,7,11,23};
        System.out.println(BinarySearchMost.binaryLeft(arr,7));
        System.out.println(BinarySearchMost.binaryRight(arr,7));
    }
    /*
        返回最靠左的元素索引
     */
    public static int binaryLeft(int[] arr, int key) {
        int i = 0;
        int j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (key < arr[mid]) {
                j = mid - 1;
            } else if (key > arr[mid]) {
                i = mid + 1;
            } else {
                candidate = mid;
                j = mid -1;
            }
        }
        return candidate;
    }
    /*
    返回最靠右的元素索引
 */
    public static int binaryRight(int[] arr, int key) {
        int i = 0;
        int j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (key < arr[mid]) {
                j = mid - 1;
            } else if (key > arr[mid]) {
                i = mid + 1;
            } else {
                candidate = mid;
                i = mid +1;
            }
        }
        return candidate;
    }
}

运行结果

2.5 没找到返回有意义的值

package com.hh.algorithm.find;

/**
 * 当该数组找不到该元素时,返回大于(小于)等于目标的最靠左(右)的索引位置
 */
public class BinarySearchMost2 {

    public static void main(String[] args) {
        int[] arr = {1,2,4,5,7,7,7,7,11,23};
        System.out.println(BinarySearchMost2.binaryLeft(arr,3));
        System.out.println(BinarySearchMost2.binaryRight(arr,9));
    }
    /*
        返回大于目标的最靠左索引
     */
    public static int binaryLeft(int[] arr, int key) {
        int i = 0;
        int j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (key <= arr[mid]) {
                j = mid - 1;
            } else{
                i = mid + 1;
            }
        }
        return i;
    }
    /*
    返回最小于目标的最靠右索引
 */
    public static int binaryRight(int[] arr, int key) {
        int i = 0;
        int j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (key < arr[mid]) {
                j = mid - 1;
            } else {
                i = mid +1;
            }
        }
        return i-1;
    }
}

运行结果

本文为学习笔记,所参考文章均已附上链接,若有疑问请私信!

创作不易,如果对你有点帮助的话麻烦点个赞支持一下!

新手小白,欢迎留言指正!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547000.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

解决调用相同url数据不刷新问题

原代码 原因 谷歌浏览访问相同接口默认调用缓存数据 解决方案 添加时间戳

WebKit简介及工作流程

文章目录 一、WebKit简介二、WebKit结构三、Webkit工作流程四、WebKit常见问题五、WebKit优点六、相关链接 一、WebKit简介 WebKit是一个开源的浏览器引擎&#xff0c;它的起源可以追溯到2001年&#xff0c;当时苹果公司推出了其首款基于Unix的操作系统Mac OS X。在2002年&…

科大讯飞星火开源大模型iFlytekSpark-13B GPU版部署方法

星火大模型的主页&#xff1a;iFlytekSpark-13B: 讯飞星火开源-13B&#xff08;iFlytekSpark-13B&#xff09;拥有130亿参数&#xff0c;新一代认知大模型&#xff0c;一经发布&#xff0c;众多科研院所和高校便期待科大讯飞能够开源。 为了让大家使用的更加方便&#xff0c;科…

Golang | Leetcode Golang题解之第30题串联所有单词的子串

题目&#xff1a; 题解&#xff1a; func findSubstring(s string, words []string) (ans []int) {ls, m, n : len(s), len(words), len(words[0])for i : 0; i < n && im*n < ls; i {differ : map[string]int{}for j : 0; j < m; j {differ[s[ij*n:i(j1)*n]…

分布式的计算框架之Spark(python第三方库视角学习PySpark)

基本介绍 Apache Spark是专为大规模数据处理而设计的快速通用的计算引擎 。现在形成一个高速发展应用广泛的生态系统。 特点介绍 Spark 主要有三个特点&#xff1a; 首先&#xff0c;高级 API 剥离了对集群本身的关注&#xff0c;Spark 应用开发者可以专注于应用所要做的计…

牛客网刷题:BC48 牛牛的线段

输入描述&#xff1a; 第一行输入 x1 和 y1&#xff0c;用空格隔开。 第二行输入 x2 和 y2&#xff0c;用空格隔开。 其中 x1 &#xff0c; y1 &#xff0c;x2 &#xff0c;y2 都是整数 输出描述&#xff1a; 输出线段的长度的平方 解题思路&#xff1a; 定义四个变量 用…

【黑马头条】-day06自媒体文章上下架-Kafka

文章目录 今日内容1 Kafka1.1 消息中间件对比1.2 kafka介绍1.3 kafka安装及配置1.4 kafka案例1.4.1 导入kafka客户端1.4.2 编写生产者消费者1.4.3 启动测试1.4.4 多消费者启动 1.5 kafka分区机制1.5.1 topic剖析 1.6 kafka高可用设计1.7 kafka生产者详解1.7.1 同步发送1.7.2 异…

【C 数据结构】栈

文章目录 【 1. 基本原理 】栈的分类 【 2. 动态链表栈 】2.1 双结构体实现2.1.0 栈的节点设计2.1.1 入栈2.1.2 出栈2.1.3 遍历2.1.4 实例 2.2 单结构体实现2.2.0 栈的节点设计2.2.1 入栈2.2.2 出栈2.2.3 实例 【 3. 顺序栈 】3.1 入栈3.2 出栈3.3 实例 【 1. 基本原理 】 栈&…

操作系统:进程(二)

进程的状态 进程状态反映进程执行过程的变化。这些状态随着进程的执行和外界条件的变化而转换。在三态模型中&#xff0c;进程状态分为三个基本状态&#xff0c;即运行态&#xff0c;就绪态&#xff0c;阻塞态。 一个进程从创建而产生至撤销而消亡的整个生命期间&#xff0c;…

【图像分类】基于深度学习的轴承和齿轮识别(ResNet网络)

写在前面: 首先感谢兄弟们的关注和订阅,让我有创作的动力,在创作过程我会尽最大能力,保证作品的质量,如果有问题,可以私信我,让我们携手共进,共创辉煌。(专栏订阅用户订阅专栏后免费提供数据集和源码一份,超级VIP用户不在服务范围之内,不想订阅专栏的兄弟们可以私信…

java的深入探究JVM之类加载与双亲委派机制

前言 前面学习了虚拟机的内存结构、对象的分配和创建&#xff0c;但对象所对应的类是怎么加载到虚拟机中来的呢&#xff1f;加载过程中需要做些什么&#xff1f;什么是双亲委派机制以及为什么要打破双亲委派机制&#xff1f; 类的生命周期 类的生命周期包含了如上的7个阶段&a…

A complete evaluation of the Chinese IP geolocation databases(2015年)

下载地址:A Complete Evaluation of the Chinese IP Geolocation Databases | IEEE Conference Publication | IEEE Xplore 被引用次数:12 Li H, He Y, ** R, et al. A complete evaluation of the Chinese IP geolocation databases[C]//2015 8th International Conference…

MyBatis 源码分析系列文章导读

1.本文速览 本篇文章是我为接下来的 MyBatis 源码分析系列文章写的一个导读文章。本篇文章从 MyBatis 是什么&#xff08;what&#xff09;&#xff0c;为什么要使用&#xff08;why&#xff09;&#xff0c;以及如何使用&#xff08;how&#xff09;等三个角度进行了说明和演…

异地组网如何安装?

【天联】是一款强大的异地组网安装工具&#xff0c;可以帮助企业实现远程设备的统一管理和协同办公。以下是【天联】可以应用的一些场景&#xff1a; 零售、收银软件应用统一管理&#xff1a;【天联】可以结合医药、餐饮、商超等零售业的收银软件&#xff0c;实现异地统一管理。…

TongRds docker 镜像做成与迁移(by liuhui)

TongRds docker 镜像做成与迁移 一&#xff0c;使用 docker commit 命令制作 TongRds docker 镜 像 1.1 拉取基础镜像 centos 并运行该镜像 拉取镜像&#xff1a;docker pull ubuntu 镜像列表&#xff1a;docker images 运行镜像&#xff1a;docker run -itd --name myubuntu…

吴恩达2022机器学习专项课程(一) 第二周课程实验:使用 scikit-learn 进行线性回归(Lab_05 Lab_06)

目标 使用scikit-learn实现线性回归(SGDRegressor和LinearRegression)。 1.什么是scikit-learn? 一个用于 Python 编程语言的开源机器学习库,用于实现各种机器学习算法。 2.特征缩放&#xff08;Z标准化&#xff09; 第一步先使用Z标准化处理训练样本&#xff0c;减少训练…

C#创建随机更换背景图片的窗体的方法:创建特殊窗体

目录 一、涉及到的知识点 1.图片资源管理器设计Resources.Designer.cs 2.把图片集按Random.Next方法随机化 3.BackgroundImage属性 二、实例设计 1. Resources.Designer.cs 2.Form1.Designer.cs 3.Form1.cs 4.生成效果 很多时候&#xff0c;我们需要每次打开窗体时能够…

项目三:学会如何使用python爬虫请求库(小白入门级)

根据上一篇文章我们学会的如何使用请求库和编写请求函数&#xff0c;这一次我们来学习一下爬虫常用的小技巧。 自定义Headers Headers是请求的一部分&#xff0c;包含了关于请求的元信息。我们可以在requests调用中传递一个字典来自定义Headers。代码如下 import requests h…

如何做一个springboot的starter类型的SDK

关键的东西 首先我们是一个starter类型的SDK&#xff0c;为了给调用者使用&#xff0c;其中有一些Bean我们会放到SDK中&#xff0c;并且这些Bean能够注入到调用者的Spring容器中。 最关键的spring.factories文件 这个文件所在位置如下图所示&#xff0c;该文件通过写入一下代…

六、新闻主题分类任务

以一段新闻报道中的文本描述内容为输入&#xff0c;使用模型帮助我们判断它最有可能属于哪一种类型的新闻&#xff0c;这是典型的文本分类问题。我们这里假定每种类型是互斥的&#xff0c;即文本描述有且只有一种类型&#xff0c;例如一篇新闻不能即是娱乐类又是财经类&#xf…