二分法查找及其变形 Java 实现（推荐）

描述：

给定一个数组

arr

，和需要查找的数

value

。

文章目录

• 1. 数据有序且无重复，查找给定值
• 2. 数据有序且有重复，查找第 1 个给定的值
• 3. 数据有序且有重复，查找最后一个值等于给定值的元素
• 4. 数据有序且有重复，查找第一个大于等于给定值的元素
• 5. 数据有序且有重复，查找最后一个小于等于给定值的元素

1. 数据有序且无重复，查找给定值

前提条件：

1.数组为升序排列

2.不存在重复的数据

算法时间复杂度：

当 n/2k = 1 时, k 是总共缩小的次数,而每一次缩小操作只涉及两个数据的大小比较,经过 k 次区间缩小的操作,时间复杂度就是O(k),n/2k = 1得到 k=log2 n ,故时间复杂度就是 O(logn)。

算法核心思想：

• 定义两个变量， low = 0, high = arr.length - 1,则 mid=low+(high - low)/2。
• 如果 value == arr[mid]，中间值正好等于要查找的值，则返回下标，return mid;
• 如果 value < arr[mid]，要找的值小于中间的值，则再往数组的小端找，high=mid-1;
• 如果 value > arr[mid]，要找的值大于中间的值，则再往数组的大端找，low=mid+1;

代码实现：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于计算机的位运算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			if(value == arr[mid]) {
				return mid;
			}else if(value > arr[mid]) {
				low = mid+1;	
			}else{
			//value < arr[mid]
				high = mid-1;
			}
		}
		return -1;//没有找到返回-1
	}
}
           

2. 数据有序且有重复，查找第 1 个给定的值

代码实现：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于计算机的位运算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			if(value == arr[mid]) {
			// 因为要找第一个出现的元素 value，若找到的元素与 value 值相同但不是第一个出现的元素，则视其为比 value 大的元素，继续缩小搜索区间，即将 high = mid -1 继续查找。
				// arr[mid-1] != value ，表示找到了第一个出现的 value。
				if(mid == 0 || arr[mid-1] != value){
					return mid;
				}else{
					high = mid - 1; 
				}
			}else if(value > arr[mid]) {
				low = mid+1;	
			}else{
			//value < arr[mid]
				high = mid-1;
			}
		}
		return -1;//没有找到返回-1
	}
}
           

3. 数据有序且有重复，查找最后一个值等于给定值的元素

代码实现：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于计算机的位运算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			if(value == arr[mid]) {
			// 因为要找最后一个出现的元素 value，若找到的元素与 value 值相同但不是最后一个出现的元素，则视其为比 value 小的元素，继续缩小搜索区间，即将 low = mid+1 继续查找。
				// arr[mid+1] != value ，表示找到了第一个出现的 value。
				if(mid == n-1 || arr[mid+1] != value){
					return mid;
				}else{
					low = mid + 1; 
				}
			}else if(value > arr[mid]) {
				low = mid+1;	
			}else{
			//value < arr[mid]
				high = mid-1;
			}
		}
		return -1;//没有找到返回-1
	}
}
           

4. 数据有序且有重复，查找第一个大于等于给定值的元素

代码实现：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于计算机的位运算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			// 这里已经不是要找一个与给定值相等元素，而是不等于的关系，所以要转换判定条件。
			if(arr[mid] >= value) {
				// 找到一个大于等于给定值的元素,还要继续判定是否是第一个。
				if(mid == 0 || arr[mid-1] < value){
					return mid;
				}else{
					high = mid - 1; 
				}
			}else{
			//arr[mid] < value 
				low = mid+1;
			}
		}
		return -1;//没有找到返回-1
	}
}
           

5. 数据有序且有重复，查找最后一个小于等于给定值的元素

代码实现：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于计算机的位运算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			 // 这里已经不是要找一个与给定值相等元素，而是不等于的关系，所以要转换判定条件。
			if(arr[mid] <= value) {
				// 找到一个小于等于给定值的元素,还要继续判定是否是最后一个。
				if(mid == n-1 || arr[mid+1] > value){
					return mid;
				}else{
					low = mid+1; 
				}
			}else{
			//arr[mid] > value 
				high = mid-1;
			}
		}
		return -1;//没有找到返回-1
	}
}
           

参考链接：算法–二分查找–查找给定条件的值 https://blog.csdn.net/qq_21201267/article/details/89339488