二分搜索——在有序数组中找到目标函数出来的最左端的位置
程序员文章站
2022-03-13 12:27:59
...
案例二:在数组中找到目标函数出来的最左端的位置
用上述数组来举例说明过程:目标函数为3,用res来记录最后找到目标元素的位置,初始为-1,表示目标函数不存在。
把目标函数3和最中间的元素4做比较,4比3大,则抛弃数组的右半部分(包括最中间的4),接下来找到数组剩下部分 1 2 3 3 3 3 4的中间值和3作比较,相等,则更新res的值,res=3;但是由于不确定是否是最左边的,所以再右半部分,接着在 1 2 3中找中间值和3做比较。由于2小于3,则说明目标函数在2的右边,把2右边的元素和3做比较,相等,则更新res=2,此时只有一个数了,所以res是最终的结果。
此题还有另一种方法:那就是将数组从左至右遍历和目标函数做比较,但是这种方法的复杂度为O(n)
二分搜索的复杂度为O(logn)
public class LeftLocationOfNum {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr1={1};
int[] arr2={1,3,2};
int[] arr3={1,2,3,3,3,3,4};
int[] arr4={1,2,2,3,3,3,4};
int[] arr5={1,2,2,2,3,3,4};
System.out.println(getLeftIndex(arr1,3));
System.out.println(getLeftIndex(arr2,3));
System.out.println(getLeftIndex(arr3,3));
System.out.println(getLeftIndex(arr4,3));
System.out.println(getLeftIndex(arr5,3));
}
public static int getLeftIndex(int[] arr, int k){
if(arr==null||arr.length==0)
return -1;
int res=-1; //用来记录最后找到目标元素的位置
int left=0;
int right=arr.length-1;
int mid=0;
int len=arr.length;
while(len>0){
mid=left + (right - left) / 2;
if(k<=arr[mid]){
res=mid;
right=mid-1;
}
else if(k>arr[mid]){
left=mid+1;
}
len=right-left+1; //更新数组的长度
}
return res;
}
}
上一篇: mysql中如何批量注释sql语句