数据结构与算法(8)_二分查找

发表于 | 分类于

二分查找

二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想.每次都通过跟区间的中间元素对比,将待查找的数据的区间缩小为原先的一半 直到找到要查找的元素,或者区间被缩小为0.

O(logn)的查找速度.

二分查找是一种非常高效的查找算法,时间复杂度是O(logn).这种对数时间复杂度,是一种极其高效的时间复杂度,有的时候甚至比常量级O(1)的算法还要高效

二分查找的递归与非递归实现

最简单的情况就是有序数组中不存在重复元素.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//非递归
public static int binarySearch(int[] arr,int value){
	int low = 0;
	int height = arr.length - 1;
	while(low <= height){
		int mid = (low + height) / 2;
		if(arr[mid] == value){
			return mid;
		}else if(arr[mid] < value){
			low = mid + 1;
		}else{
			height = mid -1;
		}
	}
	retrun -1;
}

容易出错的地方

  • 循环退出条件 注意是low <= height,而不是low < height
  • mid的取值,实际上mid=(low+height)/2 这种写法是有问题的.因为如果low和height比较大的话两者之和可能就会溢出.改进方式是将mid的计算方式改为low+(height-low)/2.更近一步,我们可以将除以2的操作转化成位运算low+((height-low)>>1).
  • low 和 height 的更新.注意这里的+1和-1,如果直接写成low=mid或者height=mid,就可能会发生死循环.
1
2
3
4
5
6
7
8
9
10
11
12
13
//递归方式
public static int binarySearchOfRecursion(int[] arr,int value,int low,int height){
	if(low > height) return -1;
	int mid = low + ((height - low) >> 1);
	if(arr[mid] == value){
		return mid;
	}
	if(arr[mid] < value){
		return binarySearchOfRecursion(arr,value,mid+1,height);
	}else{
		return binarySearchOfRecursion(arr,value,low,mid-1);
	}
}

二分查找的局限性

首先,二分查找依赖的是顺序表结构,简单说就是数组.

二分查找能否依赖其他数据结构呢?比如说链表呢?答案是否定的.主要原因是二分查找需要按照下标随机访问元素.数组随机访问时间复杂度是O(1),而链表是O(n).如果数据使用链表存储,二分查找时间复杂度会变的很高.

其次,二分查找针对的是有序数据

二分查找的数据必须是有序的.如果无序,我们需要先排序,排序的最低时间复杂度是O(nlogn).所以,如果我们针对的是一组静态数据,没有频繁的插入,删除,我们可以进行一次排序,多次二分查找.

但是,如果数据集合有频繁的插入和删除,想要使用二分查找,要么每次操作之后,保证数据依然有序;要么每次查找前都先排序.

所以,二分查找只能用在插入,删除操作不频繁,一次排序多次查找的场景中.针对动态变化的数据,二分查找,并不适用.

数据量太少不适合二分查找

如果数据量太很少,完全没必要用二分查找,顺序遍历就够了. 但是,如果数据之间比较操作非常耗时,不管数据量大小都推荐适用二分查找.

数据量太大也不适合二分查找

二分查找底层需要依赖数组这种数据结构,而数组为了支持随机访问特性,要求内存空间需要连续.太大的数据需要更多的连续内存空间,数据存储比较吃力,所以不推荐.

二分查找变体

变体1,查找一个值等于给定值的元素

有序集合中存在重复数据,我们希望第一个值等于给定值的顺序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int binarySearch1(int[] arr, int value){
	int low = 0;
	int height = arr.length - 1;
	while(low<=height){
		int mid = low + ((height-low)>>1);
		if(arr[mid] > value){
			height = mid - 1;
		}else{
			low = mid + 1;
		}else{
			if((mid == 0) || (arr[mid - 1] != value)) return mid;
			else hight = mid-1;
		}
	}
	return -1;
}

arr[mid]跟要查找的value的大小关系有三种情况:大于,小于,等于.大于,小于情况下的代码好理解.等于的情况下代码怎么理解呢?

我们重点看等于情况下的代码,如果mid=0,那这个元素就是数据的第一个元素那肯定是我们要找的;如果mid不等于0,但arr[mid]的前一个元素arr[mid-1]不等于value,那说明arr[mid]是我们要找的.

如果arr[mid-1]也等于value,那arr[mid]肯定不是我们要找的.那我们就更新height=mid - 1.因为要找的元素肯定在[low,mid-1]之间.

变体2,查找最后一个值等于给定的元素

跟变体1相似.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int binarySearch2(int[] arr,int value){
	int low = 0;
	int height = arr.length - 1;
	while(low <= height){
		int mid = low + ((height-low)>>1);
		if(arr[mid] < value){
			low = mid + 1;
		}else if(arr[mid] > value){
			height = mid - 1;
		}else{
			if((mid == arr.length - 1) || (arr[mid + 1] != value)){
				return mid;
			}else {
				low = mid + 1;
			}
		}
	}
	return -1;
}

变体3,查找第一个大于等于给定值的元素

例如: a[] = {1,2,3,5,6}.如果查找第一个大于等于4的元素,那就是5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch2(int[] arr,int value){
	int low = 0;
	int height = arr.length - 1;
	while(low <= height){
		int mid = low + ((height - low) >> 1);
		if(arr[mid] >= value){
			if(mid == 0 || arr[mid - 1] < value){
				return mid;
			}else {
				height = mid -1;
			}
		}else{
			low = mid + 1;
		}
	}
	return -1;
}

变体4, 查找最后一个小于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch2(int[] arr,int value){
	int low = 0;
	int height = arr.length - 1;
	while(low <= height){
		int mid = low + ((height - low) >> 1);
		if(arr[mid] > value){
			height = mid - 1;
		}else{
			if(mid == arr.length-1 || arr[mid + 1] > value){
				return mid;
			}else{
				low = mid + 1;
			}
		}
	}
	return -1;
}