总结朴素二分查找的模版
朴素二分查找是一种在有序数组中查找目标元素的算法。它每次比较中间元素,根据比较结果排除一半不可能存在目标值的区间,从而不断缩小查找范围。
-
前提条件: 数组必须有序(通常为升序)。
-
核心思想: 每次取中间值,将查找范围缩小一半。
-
时间复杂度: \(O(\log n)\)。
-
空间复杂度: \(O(1)\)。
-
返回结果: 找到目标值就返回下标,否则返回
-1
一,二分查找

题目解析:
简单的方式当然就是全部遍历一遍然后找到那个目标值,对于二分查找的话就是先将数组排序,然后我们先通过左右下标的形式找到中间的那一个数,然后让这个数和我们的目标值作比较,如果大了那么左边的所有区间肯定就都小了,就可以直接去除一半的空间,大了也是一样的原理,知道找到那个目标值为止
代码演示:
public int search(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while (left<=right){
int mid=left+(right-left)/2;
if (nums[mid]>target){
right=mid-1;
} else if (nums[mid]<target) {
left=mid+1;
}else return mid;
}
return -1;
}
二,在排序数组中寻找元素的第一个和最后一个位置

题目解析:
针对这道题目我们需要的是根据左端点以及右端点进行分类讨论,并且还需要注意的是求中点的方式以及循环条件

代码演示:
public int[] searchRange(int[] nums, int target) {
int[]ret=new int[2];
ret[0]=ret[1]=-1;
if (nums.length==0){
return ret;
}
//先找左端点
int left=0;
int right=nums.length-1;
while (left<right){
int mid=left+(right-left)/2;
if (nums[mid]>=target){
right=mid;
} else{
left=mid+1;
}
}
if (nums[left]!=target){
return ret;
}else{
ret[0]=left;
}
//先找右端点
left=0;
right=nums.length-1;
while (left<right){
int mid=left+(right-left+1)/2;
if (nums[mid]<=target){
left=mid;
} else{
right=mid-1;
}
}
ret[1]=right;
return ret;
}
转载自 CSDN-专业IT技术社区
原文链接:https://blog.csdn.net/java_nnnn/article/details/168967590




