二分搜索以及其扩展形式

欢迎探讨,如有错误敬请指正

如需转载,请注明出处 http://www.cnblogs.com/nullzx/


二分搜索使用的前提是数组必须有序,在本文中,我们用lo(low)表示查找范围的起始下标,hi(hight)表示查找范围的结束下标,mid表示lo和hi的中间位置。

1. 一般情况二分搜索

现在我们来看正常的二分搜索,我们来讨论一下如果没有找到这这个元素时,lo和hi下标的元素值和key的大小关系。如果没有找到key,最后一个查找的位置一定是lo == hi的位置,下标lo之前元素的一定比key小,下标hi之后元素的一定比key大。如果当前位置(即lo和hi的下标)比key大,hi减小1;如果当前位置比key小,lo增加1。总之lo会比hi大1,结束循环。如果没有找到key,lo和hi两者之一有可能越界,hi越界时 hi为-1,lo越界时lo为a.length。在没有越界的情况下,循环结束以后,a[hi] < key,a[lo] > key。所以, 如果没有找到这这个元素,a[hi]是小于key中最接近key的值,a[lo]是大于key中最接近key的值。

2. 最小下标二分搜索

问题:如果不存在key,返回-1, 如果存在key,返回和key相等的元素中的最小的下标。

思路:如果a[mid] == key 则用lastFind记录下mid,然后在[lo, mid-1]中继续继续查找,如果在这个新范围内还能找到和key相等的元素下标,则替换lastFind,然后更新lo和hi,继续迭代上述过程,直到lo > hi;如果没有找到,lastFind就是最小下标 。

同理,最大下标二分搜索,如果a[mid] == key 则用lastFind记录下mid,然后在[mid+1,hi]中继续继续查找,……

3. 小于key的元素个数

整个数组中的元素可以分为两种,大于等于key的和小于key的。如果a[mid] >= key下一个查找的范围是[lo, mid-1],如果a[mid] < key下一个查找的范围是[mid+1, hi], 直到lo > hi 才退出循环。最后一个查找的位置一定是lo == hi的位置,lo下标之前的一定小于key,hi下标之后的一定大于等于key。如果当前位置(即lo和hi的下标)的元素值大于等于key,hi减小1;如果当前位置小于key小,lo增加1。所以当循环结束时,lo之前下标的元素都是小于key的,而这些元素的个数等于lo。

同理,我们可以解决大于key的元素个数的问题。

4. 小于等于key的元素个数

整个数组中的元素可以分为两种,大于key的和小于等于key的。如果a[mid] > key下一个查找的范围是[lo, mid-1],如果a[mid] <= key下一个查找的范围是[mid+1, hi],直到lo > hi 才退出循环。最后一个查找的位置一定是lo == hi的位置,lo下标之前的一定小于等于key,hi下标之后的一定大于key。如果当前位置(即lo和hi的下标)的元素值大于key,hi减小1;如果当前位置小于等于key小,lo增加1。所以当循环结束时,lo之前下标的元素都是小于等于key的,而这些元素的个数等于lo。

同理,我们可以解决大于等于key的元素个数的问题。

5.小于等于key中下标最大

思路类似,不在赘述,但要注意lo和hi越界的情况

6.源代码

package interview_question;

public class BinarySearch {
	
	/*普通二分搜索,如果找到key,返回任意一个和key相等的元素下标,否则返回-1*/
	public static int find(int[] a, int key){
		
		int lo = 0, hi = a.length - 1;
		
		while(lo <= hi){
			
			int mid = (lo + hi) / 2;
			
			if(a[mid] > key){
				hi = mid - 1;
			}else if(a[mid] < key){
				lo = mid + 1;
			}else{
				return mid;
			}
		}
		
		return -1;
	}
	
	/*
	如果不存在目标元素,返回-1, 如果存在目标元素,返回和目标元素相等中下标最小的
	*/
	public static int findWithMinIndex(int[] a, int key){
		
		int lo = 0, hi = a.length - 1;
		
		int lastFind = -1;
		while(lo <= hi){
			
			int mid = (lo + hi)/2;
			
			if(a[mid] > key){
				hi = mid - 1;
			}else if(a[mid] < key){
				lo = mid + 1; 
			}else{
				lastFind = mid;
				hi = mid - 1;
			}
		}
		
		return lastFind;
	}
	
	
	/*上述问题的第二种实现方法
	public static int findWithMinIndex(int[] a, int target){
		int lo = 0, hi = a.length - 1;
		while(lo <= hi){
			int mid = (lo + hi)/2;
			if(a[mid] >= target){
				hi = mid - 1;
			}else{
				lo = mid + 1;
			}
		}
		
		if(lo < a.length && a[lo] == target){
			return lo;
		}else{
			return -1;
		}
	}
	*/
	
	
	/*返回数组元素 <key 的元素个数*/
	public static int findLessCnt(int[] a, int key){
		
		int lo = 0, hi = a.length - 1;
		
		while(lo <= hi){
			
			int mid = (lo + hi)/2;
			
			if(a[mid] >= key){
				hi = mid - 1;
			}else{
				lo = mid + 1; 
			}
		}
		
		return lo;
	}
	
	
	/*返回 数组元素中 <=key 的元素个数*/
	public static int findLessEqualCnt(int[] a, int key){
		
		int lo = 0, hi = a.length - 1;
		
		while(lo <= hi){
			
			int mid = (lo + hi) / 2;
			
			if(a[mid] > key){
				hi = mid - 1;
			}else{
				lo = mid + 1;
			}
		}
		
		return  lo;
	}
	
	/*如果未找到key,返回元素值比目标小且最接近目标元素的下标*/
	public static int findLessEqual(int[] a, int key){
		
		int lo = 0, hi = a.length-1;
		
		/*排除lo和hi越界的情况*/
		if(a[lo] >= key){
			return lo;
		}
		
		if(a[hi] <= key){
			return hi;
		}
		
		while(lo <= hi){
			
			int mid = (lo + hi)/2;
			
			if(a[mid] >= key){
				hi = mid - 1;
			}else if(a[mid] < key){
				lo = mid + 1;
			}
		}
		
		return a[lo] == key ? lo : hi;
	}
}

相关推荐