二分查找是一种简单的快速查找方法。我们假设有10个订单,订单金额分别是:8,11,19,23,27,33,45,55,67,98。利用二分思想,每次都与中间数据比较,缩小查找区间的范围。
如下图,比如要查找元素11:
二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。
假设数据大小是n,每次查找后,数据都会缩小为原来的一半,最坏情况下,直到查找区间被缩小为空。
n/2k = 1时,k的值就是缩小的次数,所以k=logn,时间复杂度是O(logn)。
二分查找的实现
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
二分查找的局限性
首先,二分查找依赖的是顺序表结构,就是数组。其次,二分查找针对的是有序数据。再次,数据量太小不适合二分查找,因为体现不出优势。最后,数据量太大也不适合二分查找,因为二分查找是作用在数组上的,而数组需要连续的存储空间。
二分查找变体
1、查找第一个值等于给定值的元素
如果使用上面的二分查找,首先拿 8 与区间的中间值 a[4] 比较,8 比 6 大,于是在下标 5 到 9 之间继续查找。下标 5 和 9 的中间位置是下标 7,a[7] 正好等于 8,所以代码就返回了。尽管 a[7]也等于 8,但它并不是我们想要找的第一个等于 8 的元素,因为第一个值等于 8 的元素是数组下标为 5 的元素。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
如果 mid 等于 0,那这个元素已经是数组的第一个元素,那它肯定是我们要找的;如果 mid 不等于 0,但 a[mid]的前一个元素 a[mid-1]不等于 value,那也说明 a[mid]就是我们要找的第一个值等于给定值的元素。
如果经过检查之后发现 a[mid]前面的一个元素 a[mid-1]也等于 value,那说明此时的 a[mid]肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新 high=mid-1,因为要找的元素肯定出现在[low, mid-1]之间。
2、查找最后一个值等于给定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
如果 a[mid]这个元素已经是数组中的最后一个元素了,那它肯定是我们要找的;如果 a[mid]的后一个元素 a[mid+1]不等于 value,那也说明 a[mid]就是我们要找的最后一个值等于给定值的元素。
如果我们经过检查之后,发现 a[mid]后面的一个元素 a[mid+1]也等于 value,那说明当前的这个 a[mid]并不是最后一个值等于给定值的元素。我们就更新 low=mid+1,因为要找的元素肯定出现在[mid+1, high]之间。
3、查找第一个大于等于给定值的元素
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
如果 a[mid]小于要查找的值 value,那要查找的值肯定在[mid+1, high]之间,所以,我们更新 low=mid+1。
对于 a[mid]大于等于给定值 value 的情况,我们要先看下这个 a[mid]是不是我们要找的第一个值大于等于给定值的元素。如果 a[mid]前面已经没有元素,或者前面一个元素小于要查找的值 value,那 a[mid]就是我们要找的元素。
如果 a[mid-1]也大于等于要查找的值 value,那说明要查找的元素在[low, mid-1]之间,所以,我们将 high 更新为 mid-1。
4、查找最后一个小于等于给定值得元素
public int bsearch7(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}