二分查找

二分查找基本实现

public int binarySearch(int[] nums, int key){
	int l = 0, h = nums.length-1;
	while(l<=h){
		int mid = l+(h-l)/2;  //防止(h+l)/2加法溢出
		if(nums[mid]==key)
			return mid;
		else if(nums[mid]>key)
			h = mid-1;
		else
			l = mid+1;
	}
	return -1;
}

变种二分查找，找出数组中key重复元素最左位置(注意边界)

public int binarySearch(int[] nums, int key){
	int l=0, h=nums.length-1;
	while(l<h){
		int mid = l+(h-l)/2;
		if(nums[mid]>=key)
			h = mid;
		else
			l = mid+1;
	}
	if(nums[l]==key)
		return l;
	else 
		return -1;
}

leetcode上二分查找题

//求开方   69. Sqrt(x) (Easy)
public int mySqrt(int x){
	if(x<=1)
		return x;
	int l=1,h=x;
	while(l<=h){
		int mid = l+(h-l)/2;
		int sqrt = x/mid;
		if(sqrt==mid)
			return mid;
		else if(mid>sqrt)
			h = mid-1;
		else
			l = mid+1;
	}
	return h;
}

//给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果找不到就返回第 1 个字符
//744. Find Smallest Letter Greater Than Target (Easy)
public char nextGreatestLetter(char[] letters, char target){
	int l=0, h=letters.length-1;
	while(l<=h){
		int mid = l+(h-l)/2;
		if(letters[mid]<=target)
			l = mid+1;
		else
			h = mid-1;
	}
	return l<letters.length ? letters[l] : letters[0];
}

//以O(logN)时间复杂度找出有序数组中唯一不出现2次的元素
//540. Single Element in a Sorted Array (Medium)
//假设index是该元素所在位置，mid是偶数，则当(mid+1<index)时，nums[m]==nums[m+1];
//当(mid+1>=index),nums[m]!=nums[m+1]
//因此，m为偶数的情况下，当nums[m]==nums[m+1],index所在区间应该为[m+2,h];否则，index在[l,m];
public int singleNonDuplicate(int[] nums){
	int l=0, h=nums.length-1;
	while(l<h){
		int mid = l+(h-l)/2;
		if(mid%2==1)
			mid--; //保证mid是偶数
		if(nums[mid]==nums[mid+1)
			l = m+2;
		else
			h = m;
	}
	return h;
}

//旋转数组中的最小数字 153. Find Minimum in Rotated Sorted Array (Medium)
public int findMin(int[] nums){
	int l=0, h=nums.length-1;
	while(l<h){
		int mid = l+(h-l)/2;
		if(nums[mid]<=nums[h])
			h = mid;
		else
			l = mid+1;
	}
	return nums[l];
}

//查找区间，找到最左位置，找到最右位置
//34. Search for a Range (Medium)
public int findRange(int[] nums, int target){
	int first=0, last=0;
	int l=0, h=nums.length-1;
	//找最左位置
	while(l<h){
		int mid = l+(h-l)/2;
		if(nums[mid]>=target)
			h = mid;
		else
			l = mid+1;
	}
	if(nums[l]!=target)
		return new int{-1,-1};
	else{
		first = l;
		//找最右位置
		l=0, h=nums.length-1;
		while(l<h){
			int mid = l+(h-l+1)/2;//这里mid选择向上取整，否则会死循环
			if(nums[mid]<=target)
				l = mid;
			else
				h = mid-1;
		}
		last = h;
		return new int{first, last};
	}
}

​

总结

关于while里的判断条件，如果缩小区间的形式是l = m-1 && h = m+1（即两边闭区间），那么判断条件是l<=h；否则应该是l<h