把知识记在小本本上

将零散的知识点放在一个集中的地方,不断递归重构,形成一套为己所用的知识系统。

博客首页 | 小本本首页

之前在bilibili看到一个有趣的视频,关于二分查找的。戳我看这个有趣的视频

二分思想

就如上面视频中的栗子,猜数字游戏,如果从头开始一个一个的猜是非常低效的。

在实际的开发场景中,假设有1w条订单数据,已经按照订单的金额从小到大排序,每个定干的金额不同,最小单位是元。

如果从第一个订单开始,遍历这1w条订单,直到找到目标为止,这种方法在最坏情况下可能要便利完所有数据才能找到。

但是用二分法,每次都通过跟区间中间元素对比,将整个带查找的区间缩小为之前的一半,直到查找的需要的数据或者区间缩小为0。

二分查找实现(递归和非递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 非递归实现
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;
}
}/*while*/

return -1;
}
  1. 循环退出条件:low<=high

  2. mid的取值:mid=(low+high)/2在low和high比较大的话两者之和容易溢出。

改进:low+(high-low)/2

更高效:low+((high-low)>>1)

  1. low和high的更新

low=mid+1high=mid-1这里的+1和-1,如果写成low=mid或high=mid就可能发生死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 二分查找的递归实现
int bsearch(int a[], int n, int val)
{
return b(a, 0, n - 1, val);
}

int b(int a[], int low, int high, int value)
{
if (low > high) return -1;

int mid = low + ((high - low) >> 1);
if (a[mid] == value)
{
return mid;
}
else if (a[mid] < value)
{
return bsearchInternally(a, mid+1, high, value);
}
else
{
return bsearchInternally(a, low, mid-1, value);
}
}

时间复杂度

二分查找的被查找区间缩小速度是一个等比数列,公比q为1/2。

假设数据规模为n,每次查找后数据规模都会缩小为原来的一半,最坏情况下,直到查找区间被缩小为空停止。

n/2^k=1时,k就是总共缩小的次数,每次缩小只涉及2个数据的比较,经过k次区间缩小操作,时间复杂度为O(k)。k等于以2为底n的对数,解得时间复杂度为O(logn)

O(logn)在某些情况下比O(1)时间复杂度的算法高效。O(1)时忽略掉常熟、系数和低阶。当数据规模够大时,如O(10000),此时log(n)的算法效率比O(1)的高。

局限性

  1. 二分查找依赖顺序结构

  2. 二分查找针对的是有序数据

  3. 数据量太小不适合二分查找

    比如在10个元素的数组中查找一个元素,遍历会来的更方便一些。而且查找速度也差不多。

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

    为了支持随机访问,内存空间需要连续。

二分查找的变体问题

  1. 查找第一个值等于给定值的元素

    当区间中间值不等于要查找的元素时,需要继续查找。

    当区间中间值等于要查找的元素时,看看中间值的前一个值是否等于要查找的元素,如果等则更新high=mid-1,否则现在这个元素就是要查找的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
  1. 查找最后一个值等于给定值的元素

    跟第一种一样,不过这次要和mid后面的一个元素进行比较。更新low=mid+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
  1. 查找第一个大于等于给定值的元素

    如果mid的值小于要查找的值,则目标值在[mid+1,high]之间,更新low。

    如果mid的值大于要查找的值,目标值在[low,mid-1]之间,更新high。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
  1. 查找最后一个小于等于给定值的元素

    要查找的值大于当前mid中的值,目标值在[low,mid-1]之间,更新high=mid-1。

    要查找的值小于mid+1的值,则要查找的值在[mid+1,high]之间,更新low=mid+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

数据结构与算法之美