欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分搜索——在有序数组中找到目标函数出来的最左端的位置

程序员文章站 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;
	}

}