这篇“Java中二分法怎么实现”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借免费云主机域名鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“Java中二分法怎么实现”文章吧。思路：由于是有序数组，可以先得到中点位置，中点可以把数组分为左右半边。如果中点位置的值等于目标值，直接返回中点位置。如果中点位置的值小于目标值，则去数组中点左侧按同样的方式寻找。如果中点位置的值大于目标值，则取数组中点右侧按同样的方式寻找。如果最后没有找到，则返回：-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了在本问题中，因为要找到最左侧的位置，所以，在遇到相等的时候，只需要先把位置记录下来，不用直接返回，然后继续去左侧找是否还有满足条件的更左边的位置。同时，在遇到arr[m] > t条件下，也需要记录下此时的m位置，因为这也可能是满足条件的位置。代码：整个算法的时间复杂度是O(logN)。思路本题也是用二分来解，当通过二分找到某个元素的时候，不急着返回，而是继续往左（右）找，看能否找到更左（右）位置匹配的值。代码如下：时间复杂度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，如果中点位置的值比左右两边的值都大:则mid位置即峰值位置，直接返回。否则，有如下两种情况：情况一：mid 位置的值比 mid – 1 位置的值小趋势如下图：则在[1...(mid-1)]区间内继续二分。情况二：mid 位置的值比 mid + 1 位置的值小趋势是：则在[(mid+1)...(N-2)]区间内继续上述二分。完整代码时间复杂度O(logN)。以上就是关于“Java中二分法怎么实现”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注百云主机行业资讯频道。
这篇文章主要介绍“html中怎么引用css文件”，在日常操作中，相信很多人在html中怎么引用css文件问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”html中怎么引用css文件”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
