首页 > 编程语言 >java与算法基础(二) 二分查找

java与算法基础(二) 二分查找

时间:2023-12-25 20:11:43浏览次数:53  
标签:二分 Right java target nums int 查找 right left

二分查找基本算法

用于查找已排列数组,且一般没有重复数

左闭右开

查找区间为 [ Left , Right ) ,比较Left和Right中间的那个数和Target的。如果中间数大于target,将Left设为Middle-1;如果中间数小于target,将Right设为Middle

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;//因为是左开右闭,[Left,Right)
        while (left < right) {// 因为left == right的时候,在[left, right)是无效的空间
            int mid = left + ((right - left) / 2);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }
}

左闭右闭

查找区间为 [ Left , Right ] ,比较Left和Right中间的那个数和Target的。如果中间数大于target,将Left设为Middle-1;如果中间数小于target,将Right设为Middle+1

 public int search(int[] nums, int target) {
        int Left = 0; // 左初始化为最左边一格
        int Right = nums.length - 1; // 左初始化为最右边一格

        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[Left] || target > nums[Right])
            return -1;
        while (Left <= Right) {
            int Middle = Left + (Right - Left) / 2;
            if (nums[Middle] < target)
                Left = Middle + 1;
            else if (nums[Middle] > target)
                Right = Middle - 1;
            else
                return Middle;
        }
        return -1;
    }

此外,观察到如果target不在数组里。循环结束后,Left是比这个数大的数里最小的,Right是比这个数小的数里最大的

在排序数组中查找元素的第一个和最后一个位置

题目:

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]

可以通过两次二分查找(左闭右闭),分别查找左边界和有边界。先设左右边界为-1,若寻找到target再赋其他值。左边界既先找到等于目标的数并假令左边界为这个数,再令Right=Middle-1 继续寻找左边是否依然有等于target的数。右边界寻找同理。

 public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int LeftSearch = -1;
        int RightSearch = -1;
        // 计算左边界(既:二分查找找到最左边的等于target的数)
        while (left <= right) {
            int midle = left + (right - left) / 2;
            if (nums[midle] < target) {
                left = midle + 1;
            } else if (nums[midle] > target) {
                right = midle - 1;
            } else if (nums[midle] == target) {
                /* 若匹配到target,先假令第一个数等于middle
                再查找左半边有没有依然等于target的 */
                LeftSearch = midle;
                right = midle - 1;
            }
        }
        //
        left = 0;
        right = nums.length - 1;
        // 计算右边界(既:二分查找找到最右边的等于target的数)
        while (left <= right) {
            int midle = left + (right - left) / 2;
            if (nums[midle] < target) {
                left = midle + 1;
            } else if (nums[midle] > target) {
                right = midle - 1;
            } else if (nums[midle] == target) {
            /*若匹配到target,先假令最后一个数等于middle
                再查找右半边有没有依然等于target的*/  
                RightSearch = midle;
                left = midle + 1;
            }
        }

        return new int[] { LeftSearch, RightSearch };
    }

标签:二分,Right,java,target,nums,int,查找,right,left
From: https://www.cnblogs.com/alienus/p/17926885.html

相关文章

  • Java技术得这样进阶,天天CRUD就完蛋了
    Java天天CRUD,技术没提高怎么办?技术进阶得这么搞,才能进阶为高级开发和架构师?资料地址:自学精灵-IT技术星球(也可以百度搜:自学精灵)。首先点明,只写业务代码是无法成长技术的。提升技术的两个方法是:有技术大佬带有技术大佬的资料本文介绍靠谱的技术进阶资料,让你比其他人更有竞争力!本文......
  • Java技术得这样进阶,天天CRUD就完蛋了
    ​简介Java天天CRUD,技术没提高怎么办?技术进阶得这么搞,才能进阶为高级开发和架构师!资料地址:自学精灵-IT技术星球(也可以百度搜:自学精灵)。首先点明,只写业务代码是无法成长技术的。提升技术的两个方法是:有技术大佬带有技术大佬的资料本文介绍靠谱的技术进阶资料,让你比其他人......
  • java 17 原生操作 mysql 5.7
    环境:JDK:17mysql:5.7和数据库打交道,在项目开发中是在所难免的。今天简单学习下在java中原生操作MySQL,demo通过maven做依赖管理。依赖在新建maven项目后,加入依赖:<dependencies><dependency><groupId>com.mysql</groupId><artifactId>mysql......
  • 启动springboot的测试类,报红:Java HotSpot(TM) 64-Bit Server VM warning: Sharing is
    启动springboot的测试类时,报红:JavaHotSpot(TM)64-BitServerVMwarning:Sharingisonlysupportedforbootloaderclassesbecausebootstrapclasspathhasbeenappended原因:JavaHotSpot(TM)64位服务器虚拟机已附加引导程序类路径解决办法:IDEA—》Settings—》Build......
  • 深度剖析 Spring 框架在 Java 应用开发中的优势与应用
    Spring是用于企业Java应用程序开发的最流行的应用程序开发框架。全球数百万开发人员使用SpringFramework创建高性能、易于测试和可重用的代码。SpringFramework是一个开源的Java平台。它最初由RodJohnson编写,并于2003年6月在Apache2.0许可下首次发布。为什......
  • 十七,JAVA IO 线程
    字符流:每次读写一个字符,只能操作文本文Reader:InputStreamReader是字节流通向字符流的桥梁Writer:OutputStreamWriter是字符流通向字节流的桥梁便捷流:FileReaderFileWriterFileReaderfileReader=newFileReader("file.txt");FileWriterfileWriter=......
  • java爬虫技术之Selenium爬虫
    前言Selenium爬虫是一种基于浏览器自动化的爬虫技术,可以模拟用户的操作行为,实现对动态网页的爬取。在一些情况下,为了绕过网站的反爬虫机制或者访问受限的网站,我们需要使用代理IP来进行爬取。本文将介绍如何使用Selenium爬虫结合代理IP进行网络爬取,并附带完整的代码实现。一、什么是......
  • Java多线程:深入理解Java中的死锁
    一、引言死锁是计算机科学中的一个重要概念,特别是在并发编程中。在Java中,死锁是指两个或更多的线程永久地等待对方释放资源的情况。当两个或更多的线程无限期地等待对方释放锁定的资源时,就会发生死锁。本文将通过示例和深入分析,探讨Java中的死锁问题。二、示例:银行家问题为了更好地......
  • Java中的泛型
    1.为什么要有泛型泛型可以理解为标签,比如药店里会在某一类药品处贴上标签方便寻找。定义:把元素的类型设计成一个参数,这个类型参数叫做泛型。比如List<String>这表明该List只能保存字符串类型的对象那么使用或不使用泛型有什么区别呢?看下面的代码@Testpublicvoidtest(){ArrayLis......
  • JAVA TSV文件的解析与生成
    TSV文件与CSV文件的区别TSV为用制表符tab分隔的文本文件。CSV为用逗号,分隔的文本文件。TSV文件的打开方式1.使用nodepad++等文本工具打开,使用记事本打开会导致某些行的格式错误。2.打开一个Excel,直接将tsv文件拖进去即可。JAVATSV文件的解析1.添加univocity-parsersjar包依赖 ......