vlambda博客
学习文章列表

[算法分析]二分查找细节分析与技术要点

前言

虽然我们都知道二分查找的思想,也经常用, 但是估计很多细节已经忘记了.

先贤曾经说过:

尽管二分查找的基本思想相对简单,但细节可以令人难以招架 ... — 高德纳

实现一个基本的二分查找

今天先和大家来温习一下,一个基本的二分查找是如何实现的.

首先我们设计一下函数的声明:

/// 使用二分查找,在 nums 中查找目标值 target 所在的位置索引.
/// 如果找不到返回 -1
int bsearch(vector<int> nums, int target) {
  return -1;
}

注意: nums 在上面的使用中没有使用引用,是为了写测试传值更方便.

然后少不了,一个精心准备的简单的测试用例:

TEST(bsearchTestSuite, bsearch_base) {
  EXPECT_EQ(bsearch({012345}, 6), -1);
  EXPECT_EQ(bsearch({012345}, 7), -1);
  EXPECT_EQ(bsearch({012345}, 0), 0);
  EXPECT_EQ(bsearch({012345}, 1), 1);
  EXPECT_EQ(bsearch({012345}, 2), 2);
  EXPECT_EQ(bsearch({012345}, 3), 3);
  EXPECT_EQ(bsearch({012345}, 4), 4);
  EXPECT_EQ(bsearch({012345}, 5), 5);
  
  EXPECT_EQ(bsearch({}, 1), -1);
  EXPECT_EQ(bsearch({0}, 1), -1);
  EXPECT_EQ(bsearch({1}, 1), 0);
  EXPECT_EQ(bsearch({12}, 1), 0);
  EXPECT_EQ(bsearch({12}, 2), 1);
  EXPECT_EQ(bsearch({12}, 3), -1);
}

根据二分查找的思想,我们可以写出如下代码.

int bsearch(vector<int> nums, int target) {
  int lo = 0;
  int hi = nums.size() - 1;
  while (lo <= hi) {
    int mid = (hi + lo) / 2;
    int mid_num = nums[mid];
    if (target == mid_num) {
      return mid;
    }
    if (target > mid_num) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

这里有几个细节值得注意:

  1. 循环条件是 lo<=hi ,为什么要等于? 你可以想想,比如一开始数组只有一个数字,也就是 lo==hi
  2. 如果担心 hi+lo 值太大了会溢出,也可以改写成这样.   mid = lo + (hi - lo) /2

从查找到插入

其实像上面我们的 bsearch 对于找不到的情况返回 -1 的值其实是没有什么意思的.

有意思的是返回插入位置.

因为我很可能想在二分查找后找到一个合适插入的位置.

我们先设计如下签名:

/// 在 从小到大排序 好的 nums 中搜索适合插入 x 的位置.
int search_ints(vector<int> nums, int x) {}

然后先设计如下测试用例:

  EXPECT_EQ(search_ints({}, 1), 0);
  EXPECT_EQ(search_ints({0}, 1), 1);
  EXPECT_EQ(search_ints({1}, 0), 0);
  EXPECT_EQ(search_ints({01}, 2), 2);
  EXPECT_EQ(search_ints({012}, 3), 3);

这里需要注意是:

如果将要插入的数是最大的数,返回位置就将是 nums.size()

另外再考虑如下用例:

  EXPECT_EQ(search_ints({22}, 2), 0);
  EXPECT_EQ(search_ints({122}, 2), 1);
  EXPECT_EQ(search_ints({1223}, 2), 1);

这里问题是,如果如果要插入的数在原有序数组中已经存在同样的数了,是应该在左边插入,还是应该在右边插入? 也就是是应该返回左边的索引还是右边的索引.(当然理论上,有多个相同的值的话,还存在多种中间的插入方式,但是这里只考虑在左边还是右边)

在我们上面,也是很多语言搜索算法的默认实现,也就是返回左边的插入位置索引.

使用代码实现如下:

/// 在 从小到大排序 好的 nums 中搜索适合插入 x 的位置.
int search_ints(vector<int> nums, int x) {
  int lo = 0;
  int hi = nums.size();  // 1) 细节 1: hi 取的是 nums.size()
  while (lo < hi) {      //  2) 细节 2: 循环条件变成了 lo < hi
    int mid = lo + (hi - lo) / 2;// 减少溢出风险
    if (x > nums[mid]) {
      lo = mid + 1;
    } else {
      // 3) 细节 3: hi 不再变成 mid -1, 而只是 mid
      // 为了在相等的时候再尝试继续向左走.
      hi = mid;
    }
  }
  return hi;  // lo == hi
}

这段代码有三个细节值得特别注意, 这里在注释中说明了.

上面的这个代码对应 Python bisect 模块中的 bisect.bisect_left.

如果我们需要一个 bisect_right 的算法,也就是在相同值时返回右边的插入位置.

我们也还是先整理出相应的测试用例:

TEST(BinarySearchTestSuite, SearchIntsRight) {
  EXPECT_EQ(search_ints_right({}, 1), 0);
  EXPECT_EQ(search_ints_right({0}, 1), 1);
  EXPECT_EQ(search_ints_right({1}, 0), 0);
  EXPECT_EQ(search_ints_right({01}, 2), 2);
  EXPECT_EQ(search_ints_right({012}, 3), 3);

  EXPECT_EQ(search_ints_right({22}, 2), 2);
  EXPECT_EQ(search_ints_right({122}, 2), 3);
  EXPECT_EQ(search_ints_right({1223}, 2), 3);
}

然后再给出实现如下:

int search_ints_right(vector<int> nums, int x) {
  int lo = 0;
  int hi = nums.size();  // 1) 细节 1: hi 取的是 nums.size()
  while (lo < hi) {      //  2) 细节 2: 循环条件变成了 lo < hi
    int mid = lo + (hi - lo) / 2;
    if (x >= nums[mid]) {
      lo = mid + 1;
      // 细节 3: 等于也向右走.
    } else {
      hi = mid;
    }
  }
  return hi;  // lo == hi
}

值得说明的是, 循环的退出条件其实是 lo == hi 所以,最后返回 lohi 都是没有问题的.

这里值得注意的是,对于查找插入位置:

  1. 搜索区间是左闭右开. 也就是 [lo, hi)
  2. 循环结束条件是 lo > hi
  3. hi=mid, lo=mid+1, 但是注意等值下,找右边界 lo=mid+1 找左边界 hi=mid

对于 C++ 20 来说, 与之相对应的函数在标准库<algorithm>中也有提供,名字叫:

std::lower_boundstd::upper_bound

搜索上下界的使用小技巧

在上面的例子中我介绍了,为了处理等值情况的插入位置,分为了 search_leftsearch_right.

  1. 判断是否值存在? 我们利用前面的 search_ints 也就是 search_ints_left 将我们的 bsearch 改写如下:

    /// 使用二分查找,在 nums 中查找目标值 target 所在的位置索引.
    /// 如果找不到返回 -1
    int bsearch(vector<int> nums, int target) {
      int lo = search_ints(nums, target);
      if (lo != nums.size() && nums[lo] == target) {
        return lo;
      }
      return -1;
    }
  2. 找到比 x 小的最大值.

    bool find_lt(vector<int> nums, int x, int& out) {
      int i = search_ints(nums, x);
      if (i > 0) {
        out = nums[i - 1];
        return true;
      }
      return false;
    }

  3. 找到数组最右边的小于等于 x 的值.

    bool find_le(vector<int> nums, int x, int& out) {
      int i = search_ints_right(nums, x);
      if (i > 0) {
        out = nums[i - 1];
        return true;
      }
      return false;
    }
  4. 找到数组最左边的大于x 的值.

    bool find_gt(vector<int> nums, int x, int& out) {
      int i = search_ints_right(nums, x);
      if (i != nums.size()) {
        out = nums[i];
        return true;
      }
      return false;
    }
  5. 找到数组中最在边的大于等于x 的值.

    bool find_ge(vector<int> nums, int x, int& out) {
      int i = search_ints(nums, x);
      if (i != nums.size()) {
        out = nums[i];
        return true;
      }
      return false;
    }

小结

尽管二分查找的基本思想相对简单,但细节可以令人难以招架,本文通过详细分析了二分查找的一些细节 ,区间的处理,循环条件的判断,希望对你掌握二分查找能有一点帮助.

后记

月亮走了,星星会掉眼泪吗? --永远怀念我的小月儿.