二分查找--查找重复有序数组中最左边的target
程序员文章站
2024-03-15 20:28:42
...
二分查找是在面试中经常会遇到的面试题,根据普通的二分查找还衍生出了二分查找的其他情况,比如有序数组中的目标出现多次,利用二分查找返回在最左边出现的目标值或者是最右边出现的目标值。
查找最左边出现的目标值
public static int binarySearchLeft(int[] arr,int target){
if(arr==null||arr.length==0){
return -1;
}
int left = 0;
int right = arr.length-1;
while(left<right){
int mid = (left+right)/2;
if(arr[mid]<target){
left = mid+1;
}else {
right = mid;
}
}
if(arr[right]==target){
return right;
}
return -1;
}
查找最右边出现的目标值
public static int binarySearchRight(int[] arr,int target){
if(arr==null||arr.length==0){
return -1;
}
int left = 0;
int right = arr.length-1;
while(left<right){
int mid = (left+right)/2;
if(arr[mid]<=target){
left = mid;
}else {
right = mid-1;
}
}
if(arr[left]==target){
return left;
}
return -1;
}
END
上一篇: 查找 TopK 问题
推荐阅读
-
符号表以及在有序数组中的二分查找
-
二分查找--查找重复有序数组中最左边的target
-
编程题 - 二分搜索查找有序数组的插入位置
-
算法007:二分查找 请实现有重复数字的有序数组的二分查找,输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一
-
Java有序数组数据结构与二分查找算法的分析
-
Java有序数组数据结构与二分查找算法的分析
-
算法007:二分查找 请实现有重复数字的有序数组的二分查找,输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一
-
C语言用函数实现,二分法查找有序数组中的数,若没有返回1
-
3.24_函数实现一个整型有序数组的二分查找
-
C语言使用二分法实现在一个有序数组中查找具体的某个数字n