java二分法的算法步骤,java二分法是什么意思
本文给大家带来了一些关于java的知识，二分法是一种非常高效的算法，在计算机搜索的过程中经常用到。在这里，我们将通过实例详细谈谈二分法的基本思想和实现，希望对你有所帮助。
如何解决写爬虫IP受阻的问题？立即使用。
在一个有序数组中，找某个数是否存在
想法：
因为是有序数组，所以可以先得到中点位置，中点可以把数组分成左右两半。如果中点位置的值等于目标值，则直接返回中点位置。如果中点位置的值小于目标值，则转到数组中点的左侧，以同样的方式查找。如果中点位置的值大于目标值，则取数组中点的右侧，用同样的方法寻找。如果最后没有找到，就返回：-1。密码
类别解决方案{
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) {
返回m；
} else if (arr[m] t) {
r=m-1；
}否则{
l=m ^ 1；
}
}
return-1；
}
}时间复杂度O(logN)。
在一个有序数组中，找大于等于某个数最左侧的位置
示例1:
输入：nums=[1，3，5，6]，目标=5
输出：2
注意：如果要在数组num中插入元素5，应该插入到元素3和元素5之间的位置，也就是位置2。
示例2:
输入：nums=[1，3，5，6]，目标=2
输出：1
注意：如果要在数组num中插入元素2，应该插入到元素1和元素3之间的位置，也就是位置1。
示例3:
输入：nums=[1，3，5，6]，目标=7
输出：4
注意：如果要在数组num中插入元素7，应该插入到数组的末尾，也就是第4个位置。
从上面的例子可以看出，这个问题本质上是找在一个有序数组中，找大于等于某个数最左侧的位置，如果不存在，就返回数组长度（表示插入在最末尾位置）。
我们只需要在上面例子的基础上做简单的改动。在上面的例子中，我们找到满足条件的位置，直接返回。
if (arr[m]==t) {
返回m；
}在这个问题中，因为我们要找到最左边的位置，所以，在遇到相等的时候，只需要先把位置记录下来，不用直接返回，然后继续去左侧找是否还有满足条件的更左边的位置。
同时，在arr[m] t的条件下，也需要记录m此时的位置，因为这也可能是满足条件的位置。
代码：
类别解决方案{
public static int search insert(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；
}否则{
l=m ^ 1；
}
}
返回ans
}
}整个算法的时间复杂度为O(logN)。
在排序数组中查找元素的第一个和最后一个位置
思考
这个问题也是用二分法解决的。当你用二分法找到一个元素时，你并不急着返回，而是继续向左(右)看，看是否能找到一个与左(右)位置相匹配的值。
代码如下：
类别解决方案{
public static int[]search range(int[]arr，int t) {
if (arr==null arr.length 1) {
返回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；
}否则{
//arr[m] t
r=m-1；
}
}
返回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；
}否则{
//arr[m] t
r=m-1；
}
}
返回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]是峰值位置，会直接返回。
否则，有以下两种情况：
情况1:中间位置的值小于中间1位置的值。
趋势如下：
然后在区间[1]内继续二分法.(中1)]。
情况2:中间位置的值小于中间1位置的值。
趋势是：
上述二分法在区间[(mid 1)中继续.(N-2)]。
完全码
公共类LeetCode _ 0162 _ FindPeakElement {
public static int findpakelement(int[]nums){
if (nums.length==1) {
返回0；
}
int l=0；
int r=nums . length-1；
if (nums[l] nums[l 1]) {
返回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]){
返回mid
}
if (nums[mid] nums[mid 1]) {
l=mid 1；
} else if (nums[mid] nums[mid - 1]) {
r=中-1；
}
}
return-1；
}
}时间复杂度O(logN)。
推荐：以上《java视频教程》是对Java中二分法的基本思想和实现细节的简单了解。更多请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。