详解Java中二分法的基本思路和实现

目录
  • 在一个有序数组中,找某个数是否存在
  • 在一个有序数组中,找大于等于某个数最左侧的位置
  • 在排序数组中查找元素的第一个和最后一个位置
  • 局部最大值问题

在一个有序数组中,找某个数是否存在

思路:

  • 由于是有序数组,可以先得到中点位置,中点可以把数组分为左右半边。
  • 如果中点位置的值等于目标值,直接返回中点位置。
  • 如果中点位置的值小于目标值,则去数组中点左侧按同样的方式寻找。
  • 如果中点位置的值大于目标值,则取数组中点右侧按同样的方式寻找。
  • 如果最后没有找到,则返回:-1。

代码

class Solution {
    public int search(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
                return m;
            } else if (arr[m] > t) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}

时间复杂度 O(logN)

在一个有序数组中,找大于等于某个数最左侧的位置

示例 1:

输入: nums = [1,3,5,6], target = 5

输出: 2

说明:如果要在num这个数组中插入 5 这个元素,应该是插入在元素 3 和 元素 5 之间的位置,即 2 号位置。

示例 2:

输入: nums = [1,3,5,6], target = 2

输出: 1

说明:如果要在num这个数组中插入 2 这个元素,应该是插入在元素 1 和 元素 3 之间的位置,即 1 号位置。

示例 3:

输入: nums = [1,3,5,6], target = 7

输出: 4

说明:如果要在num这个数组中插入 7 这个元素,应该是插入在数组末尾,即 4 号位置。

通过上述示例可以知道,这题本质上就是求在一个有序数组中,找大于等于某个数最左侧的位置,如果不存在,就返回数组长度(表示插入在最末尾位置)

我们只需要在上例基础上进行简单改动即可,上例中,我们找到满足条件的位置就直接return

if (arr[m] == t) {
    return m;
}

在本问题中,因为要找到最左侧的位置,所以,在遇到相等的时候,只需要先把位置记录下来,不用直接返回,然后继续去左侧找是否还有满足条件的更左边的位置。

同时,在遇到arr[m] > t条件下,也需要记录下此时的m位置,因为这也可能是满足条件的位置。

代码:

class Solution {
    public static int searchInsert(int[] arr, int t) {
        int ans = arr.length;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l)>>1);
            if (arr[m] >= t) {
                ans = m;
                r = m - 1;
            } else  {
                l = m + 1;
            }
        }
        return ans;
    }
}

整个算法的时间复杂度是O(logN)

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

思路

本题也是用二分来解,当通过二分找到某个元素的时候,不急着返回,而是继续往左(右)找,看能否找到更左(右)位置匹配的值。

代码如下:

class Solution {
    public static int[] searchRange(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return new int[]{-1, -1};
        }
        return new int[]{left(arr,t),right(arr,t)};
    }
    public static int left(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int ans = -1;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
               ans = m;
               r = m - 1;
            } else if (arr[m] < t) {
                l = m +1;
            } else {
                // arr[m] > t
                r = m - 1;
            }
        }
        return ans;
    }
    public static int right(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int ans = -1;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
               ans = m;
               l = m + 1;
            } else if (arr[m] < t) {
                l = m +1;
            } else {
                // arr[m] > t
                r = m - 1;
            }
        }
        return ans;
    }
}

时间复杂度 O(logN)

局部最大值问题

思路

假设数组长度为N,首先判断0号位置的数和N-1位置的数是不是峰值位置。

0号位置只需要和1号位置比较,如果0号位置大,0号位置就是峰值位置,可以直接返回。

N-1号位置只需要和N-2号位置比较,如果N-1号位置大,N-1号位置就是峰值位置,可以直接返回。

如果0号位置和N-1在上轮比较中均是最小值,那么数组的样子必然是如下情况:

由上图可知,[0..1]区间内是增长趋势, [N-2...N-1]区间内是下降趋势。

那么峰值位置必在[1...N-2]之间出现。

此时可以通过二分来找峰值位置,先来到中点位置,假设为mid,如果中点位置的值比左右两边的值都大:

arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]

mid位置即峰值位置,直接返回。

否则,有如下两种情况:

情况一:mid 位置的值比 mid - 1 位置的值小

趋势如下图:

则在[1...(mid-1)]区间内继续二分。

情况二:mid 位置的值比 mid + 1 位置的值小

趋势是:

则在[(mid+1)...(N-2)]区间内继续上述二分。

完整代码

public class LeetCode_0162_FindPeakElement {
    public static int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int l = 0;
        int r = nums.length - 1;
        if (nums[l] > nums[l + 1]) {
            return l;
        }
        if (nums[r] > nums[r - 1]) {
            return r;
        }
        l = l + 1;
        r = r - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            }
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else if (nums[mid] < nums[mid - 1]) {
                r = mid - 1;
            }
        }
        return -1;
    }
}

时间复杂度O(logN)

到此这篇关于详解Java中二分法的基本思路和实现的文章就介绍到这了,更多相关Java二分法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 关于二分法查找Java的实现及解析

    目录 二分法查找 概述 递归实现 递归实现代码 循环实现代码(非递归) 二分法查找(递归.循环) 二分法查找 概述 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法. 但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列. 归并排序即运用了二分法的思想.首先需要一个由小到大排序好的数组,先对比中间的值,如果比要找的大,则向前找,取中间值前面的一半再找中间值再对比. 如果比要找的小,则向后找,取中间值后面的一半再取中间值再对比. 递归实现 这里,

  • Java使用二分法进行查找和排序的示例

    实现二分法查找 二分法查找,需要数组内是一个有序的序列 二分查找比线性查找:数组的元素数越多,效率提高的越明显 二分查找的效率表示:O(log2N) N在2的M次幂范围,那查找的次数最大就是M,  log2N表示2的M次幂等于N, 省略常数,简写成O(logN) 如有一个200个元素的有序数组,那么二分查找的最大次数: 2^7=128, 2^8=256, 可以看出7次幂达不到200,8次幂包括, 所以最大查找次数就等于8 //循环,二分查找 static int binarySearch(int

  • java 二分法算法的实例

    java 二分法算法的实例 1.前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现.所以

  • java 中二分法查找的应用实例

    java 中二分法查找的应用实例 二分查找的前提是:数组有序 注意:mid的动态变化,否则出错!!! 实例代码: public class BiSearch { public static void main(String[] args) { new BiSearch().biFind(new int []{1,2,3,4,5,6,7},3); } public void biFind(int arr[],int y){ int start=0; int end=arr.length-1; in

  • java实现二分法的完整代码

    二分法查找,顾名思义就是要将数据每次都分成两份然后再去找到你想要的数据,我们可以这样去想,二分法查找很类似与我们平时玩的猜价格游戏,当你报出一个价格时裁判会告诉你价格相对于真实值的高低,倘若是低了那我们一定会再说出一个略高的价格,反之亦然.在二分法查找时要求传入的数据必须已经有序,假设现在为升序,然后每次将所寻找的值与中间值(数组左边界+(右边界-左边界)/2)作比较,大了则去寻找中间值左侧数据,小则寻找中间值右侧数据. 二分法查找比较局限性的就是只能操作一个已经排序了的数组. 方法一 下面为一

  • java 二分法详解几种实现方法

    java 二分法详解几种方法 二分查找(java实现) 二分查找 算法思想:又叫折半查找,要求待查找的序列有序.每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程.直到查找到了为止,否则序列中没有待查的关键字. 实现: 1.非递归代码 public static int biSearch(int []array,int a){ int lo=0; int hi=array.length

  • 详解Java中二分法的基本思路和实现

    目录 在一个有序数组中,找某个数是否存在 在一个有序数组中,找大于等于某个数最左侧的位置 在排序数组中查找元素的第一个和最后一个位置 局部最大值问题 在一个有序数组中,找某个数是否存在 思路: 由于是有序数组,可以先得到中点位置,中点可以把数组分为左右半边. 如果中点位置的值等于目标值,直接返回中点位置. 如果中点位置的值小于目标值,则去数组中点左侧按同样的方式寻找. 如果中点位置的值大于目标值,则取数组中点右侧按同样的方式寻找. 如果最后没有找到,则返回:-1. 代码 class Soluti

  • 详解Java中多线程异常捕获Runnable的实现

    详解Java中多线程异常捕获Runnable的实现 1.背景: Java 多线程异常不向主线程抛,自己处理,外部捕获不了异常.所以要实现主线程对子线程异常的捕获. 2.工具: 实现Runnable接口的LayerInitTask类,ThreadException类,线程安全的Vector 3.思路: 向LayerInitTask中传入Vector,记录异常情况,外部遍历,判断,抛出异常. 4.代码: package step5.exception; import java.util.Vector

  • 详解Java中hashCode的作用

    详解Java中hashCode的作用 以下是关于HashCode的官方文档定义: hashcode方法返回该对象的哈希码值.支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表. hashCode 的常规协定是: 在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改.从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致. 如果根据

  • 详解java中保持compareTo和equals同步

    详解java中保持compareTo和equals同步 摘要 : 介绍重写equlas()和comparable接口,两者进行不相同的判断.从而使两者的对应的list.indexOf()与 Collections.binarySearch()得到的不一样. 在Java中我们常使用Comparable接口来实现排序,其中compareTo是实现该接口方法.我们知道compareTo返回0表示两个对象相等,返回正数表示大于,返回负数表示小于.同时我们也知道equals也可以判断两个对象是否相等,那么

  • 详解Java中的悲观锁与乐观锁

    一.悲观锁 悲观锁顾名思义是从悲观的角度去思考问题,解决问题.它总是会假设当前情况是最坏的情况,在每次去拿数据的时候,都会认为数据会被别人改变,因此在每次进行拿数据操作的时候都会加锁,如此一来,如果此时有别人也来拿这个数据的时候就会阻塞知道它拿到锁.在Java中,Synchronized和ReentrantLock等独占锁的实现机制就是基于悲观锁思想.在数据库中也经常用到这种锁机制,如行锁,表锁,读写锁等,都是在操作之前先上锁,保证共享资源只能给一个操作(一个线程)使用. 由于悲观锁的频繁加锁,

  • 详解Java中KMP算法的图解与实现

    目录 图解 代码实现 图解 kmp算法跟之前讲的bm算法思想有一定的相似性.之前提到过,bm算法中有个好后缀的概念,而在kmp中有个好前缀的概念,什么是好前缀,我们先来看下面这个例子. 观察上面这个例子,已经匹配的abcde称为好前缀,a与之后的bcde都不匹配,所以没有必要再比一次,直接滑动到e之后即可. 那如果好前缀中有互相匹配的字符呢? 观察上面这个例子,这个时候如果我们直接滑到好前缀之后,则会过度滑动,错失匹配子串.那我们如何根据好前缀来进行合理滑动? 其实就是看当前的好前缀的前缀和后缀

  • 详解Java中字典树(Trie树)的图解与实现

    目录 简介 工作过程 数据结构 初始化 构建字典树 应用 匹配有效单词 关键词提示 总结 简介 Trie又称为前缀树或字典树,是一种有序树,它是一种专门用来处理串匹配的数据结构,用来解决一组字符中快速查找某个字符串的问题.Google搜索的关键字提示功能相信大家都不陌生,我们在输入框中进行搜索的时候,会下拉出一系列候选关键词. 上面这个关键词提示功能,底层最基本的原理就是我们今天说的数据结构:Trie树 我们先看看Tire树长什么样子,以单纯的单词匹配为例,首先它是一棵多叉树结构,根节点是一个空

  • 详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现

    目录 简介 工作过程 总体思路 实现 小根堆 Dijsktra 测试 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.注意该算法要求图中不存在负权边.对应问题:在无向图G=(V,E)中,假设每条边E(i)的长度W(i),求由顶点V0到各节点的最短路径. 工作过

  • 详解Java中异步转同步的六种方法

    目录 一.问题 应用场景 二.分析 三.实现方法 1.轮询与休眠重试机制 2.wait/notify 3.Lock Condition 4.CountDownLatch 5.CyclicBarrier 6.LockSupport 一.问题 应用场景 应用中通过框架发送异步命令时,不能立刻返回命令的执行结果,而是异步返回命令的执行结果. 那么,问题来了,针对应用中这种异步调用,能不能像同步调用一样立刻获取到命令的执行结果,如何实现异步转同步? 二.分析 首先,解释下同步和异步 同步,就是发出一个调

  • 一文详解Java中字符串的基本操作

    目录 一.遍历字符串案例 二.统计字符次数案例 三.字符串拼接案例 四.字符串反转案例 五.帮助文档查看String常用方法 一.遍历字符串案例 需求:键盘录入一个字符串,使用程序实现在控制台遍历该字符串 思路: 1.键盘录入一个字符串,用 Scanner 实现 2.遍历字符串,首先要能够获取到字符串中的每一个字符 public char charAt(int index):返回指定索引处的char值,字符串的索引也是从0开始的 3.遍历字符串,其次要能够获取到字符串的长度 public int

随机推荐