G&R Blog Release Regulation

naive 的二分搜索: 闭区间搜素 v.s. 左闭右开搜索

二分搜索通常由两种写法: [闭区间搜索] 和 [左闭右开搜索], 对于 [闭区间搜索的写法]
1.对于一个有序无重复元素的数组, 按照二分搜索的思想去模拟写, 刚开始的时候搜索的下界元素索引是0, 搜索的上界元素索引是 nums.size()-1
2.当前搜索目标索引记录为 mid, 判断 nums[mid] == target 如果搜到则返回; 如果没搜到执行变更区间操作: 上下界为当前搜索 mid + 1 或者 mid - 1
3.到最后没搜到的情况, 默认直接返回 -1
4.只适用于数组无重复元素下, 因此无法处理找左侧边界或者右侧边界的问题

// naive 二分搜索: 闭区间搜索: 搜索的是 [l, h] 区间
int binarySearch(vector<int>& nums, int target) {
  int l = 0;
  int h = nums.size() - 1;
  while (l <= h) {
    int mid = l + (h - l) / 2;
    int midNum = nums[mid];
    if (midNum == target) {
      return mid;
    } else if (midNum < target) {
      // 更新搜索区间到 [mid+1, h]
      l = mid + 1;
    } else if (midNum > target) {
      // 更新搜索区间到 [l, mid-1]
      h = mid - 1;
    }
  }
  return -1;
}

然而二分搜索还有另一种习惯的写法, 和上面的区别在于 while () 括号里面的边界更新操作为 while (l < h) , 核心思想是更改了搜索区间为左闭右开的方式, 搜索区间为 [l, h)

// naive 二分搜索: 左闭右开区间搜索: 永远搜索的是 [l, h) 区间
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int l = 0;
    int h = nums.size();
    while (l < h) {
      int mid = l + (h - l) / 2;
      int midNum = nums[mid];
      if (midNum == target) {
        return mid;
      } else if (midNum < target) {
        // 更新搜索区间到 [mid+1, h)
        l = mid + 1;
      } else if (midNum > target) {
        // 更新搜索区间到 [l, mid)
        h = mid;
      }
    }
    return -1;
  }
};

二分搜索的边界处理问题分析

二分搜索的问题在于很多边界条件的处理上是容易出错的, 处理细节问题如下:
1.while (l <= h) 用的是 while (l <= h) 还是 while (l < h) ? 有什么区别?
2.更新搜索区间是用 l = mid+1, h = mid-1 还是用 h = mid, l = mid?
3.为什么 naive 的二分搜索不能找到左侧边界或者右侧边界?
4.能否将 naive 的二分搜索和 [找左侧边界的二分搜索] 和 [找右侧边界的二分搜索] 的统一形式?

逐个分析上面的几个问题
1.while (l <= h) 用的是 while (l <= h) 还是 while (l < h) ? 有什么区别?
这里有个 [搜索区间] 的问题, 其实就是确认 [我们的搜索区间有没有完全覆盖应该被搜索的所有的区间], 在用 while (l <= h) 的设定下, 搜索区间是 [0, nums.size()-1], 在 while (l < l) 的设定下, 搜索区间是 [0, nums.size()) 我们不妨细看下里面的区别:
(i). while (l <= h) 的终止退出条件是 l == h+1, 写成区间形式就是 [h+1, h], 写个例子带入进去 [3,2], 这时候搜索区间为空的, 也不应该搜索, 这是没问题的
(ii). while (l < h) 的终止退出条件是 l == h, 写成区间形式就是 [h, h], 写个例子带入进去 [2,2] , 这时候区间是应该搜索一次的, 但是 while 循环终止推出了, 没有搜这最后一次, 因此区间 [2,2] 这一次搜索过程被遗漏掉了, 这不正确, 或者说搜索不够充分 (增加一次额外的判断就变完整的搜索了)

如果非要用 while (l < h) 这种模式搜索, 需要增加对这种情况单独处理

while (l < h) {
  // naive 的二分搜索
}
return nums[l] == target ? l : -1;

2.是用 l = mid+1, h = mid-1 还是用 h = mid, l = mid?
基于我们要搜索的 [搜索区间] 是 [l, h] 还是 [l, h), 在 mid 已经完成搜索的情况下,
(i). 闭区间搜索 [l, h] 应该去搜索左边的 [l, mid-1] 和 右边的 [mid+1, h] 这两个区间
(ii). 左闭右开区间搜索 [l, h) 应该去搜索左边的 [l, mid) 和 右边的 [mid+1, h) 这两个区间

3.基础的二分搜索算法为什么不能搜索左侧边界?
比如给出数组 nums = [1,2,2,2,3], target = 2, 用 naive 的算法返回的是索引2 (也就是第2个2), 但是如果我想得到 target 的左侧边界, 也就是索引1的这个位置, 这种问题通常出现在 [搜索有序数组中第1个出现的位置]; 或者想得到target的右侧边界, 也就是索引3, 这种问题通常出现在 [搜索有序数组中最后一个出现的位置], naive 的二分搜索算法是无法得到的

搜索左侧边界的二分搜索: 搜索第1个 >= target 的元素

搜索左侧边界的二分搜索实现原理 (基础版本), 如何做到搜索左侧边界呢? 我们想一下 naive 二分搜索做的事情, 当找到第一个 mid == target 的时候, 直接就返回了, 左边如果还有 mid == target 的值, 我们应该继续搜索而不是停下来, 如何继续搜索? 更新右侧的搜索边界为 mid
1.当找到 nums[mid] == target 时候, 右侧边界要继续缩小, 而不是直接返回索引; 缩小右侧边界的操作是 h = mid 还是 h = mid-1 呢?
(i). 如果 while 里面是 while (l <= h) 那么搜索的是 [l, h], 左右都闭的区间, 那么 h = mid-1
(ii). 如果 while 里面是 while (l < h) , 那么搜索区间是 [l, h), h = mid
2.返回的值是什么, 返回的索引是 l
3.在没有找到的情况下, 需要特殊处理返回-1的条件, 没有找到条件是什么?
(i). l >= nums.size() , 一个大于最大值的数字
(ii). 搜索目标是一个不存在在数组里面的元素, nums[l] != target

我们先看第一种的方式: 采用搜索闭区间的方式二分搜索左边界, 按照收缩右边界的思想进行边界更新

int binarySearchLowerBound(vector<int>& nums, int target) {
  int l = 0;
  int h = nums.size() - 1; 
  while (l <= h) {
    int mid = l + (h - l) / 2;
    int midNum = nums[mid];
    if (midNum == target) {
      // 持续收缩右侧边界
      h = mid - 1;
    } else if (midNum < target) {
      // 更新搜索区间 [mid+1, h]
      l = mid + 1;
    } else if (midNum > target) {
      // 更新搜索区间 [l, mid-1]
      h = mid - 1;
    }
  }
  // 没有找到的情况的特殊处理
  if (l >= nums.size() || nums[l] != target) {
    return -1;
  }
  return l;
}

再看利用搜索左闭右开的方式二分搜索左侧边界, 和搜索闭区间的方式相比, 因为搜索的是左闭右开区间 [l, h), 所以在更新有边界的时候或者在收缩有边界的时候采用的是 h = mid, 而不是 h = mid + 1

// 这里采用搜索左闭右开的方式来处理左侧边界的二分搜索
int binarySearchLowerBound(vector<int>& nums, int target) {
  int l = 0;
  int h = nums.size();  // 搜索的是左闭右开区间的方式 h = nums.size()
  while (l < h) {       // 搜索的是左闭右开区间的方式 while 里面符号用 while (l < h)
    int mid = l + (h - l) / 2;
    int midNum = nums[mid];
    if (midNum == target) {
      // 收缩右边界
      h = mid;
    } else if (midNum < target) {
      // 搜索区间是[mid+1, h)
      l = mid + 1;
    } else if (midNum > target) {
      // 搜索区间是[l, mid)
      h = mid;
    }
  }
  // 没有找到的情况的特殊处理
  if (l >= nums.size() || nums[l] != target) {
    return -1;
  }
  return l;
}

intuitively,
1.采用 while (l < h) 实质上将搜索区间转换成了 [l, h), 终止条件是 l == h, 也就是 [l, l) 为空
2.这里找到 target 的时候没有马上返回, 而是 [缩小区间的右边界] h, 在 [l, mid) 中继续搜索, 也就是说不断的向着左边收缩; 我们现在的 [搜索区间] 改成了搜索某个 [l, h) 分开二分区间也就是在搜索 [l, mid) 和 [mid+1, h)

搜索右侧边界的二分搜索: 搜索最后1个 <= target 的元素

同理, 搜索右侧边界的二分搜索, 本质上是在搜索到 target 元素的时候进行左侧的边界收缩:
1.我们先看闭区间搜索下的右侧边界二分搜索, 也就是循环写成 while (l <= h) 的这种形式, 搜索的区间始终是 [l, h], 在搜到目标 target 并收缩左侧边界时, 收缩边界的方式为 l = mid + 1
2.因为搜索的是右边界, 最终返回的结果是右边界 h
3.处理没有搜索到的情况: h 向左搜索到 < 0 或者没搜到对应的值 nums[h] != target

int binarySearchHigherBound(vector<int>& nums, int target) {
  int l = 0;
  int h = nums.size() - 1; 
  while (l <= h) {
    int mid = l + (h - l) / 2;
    int midNum = nums[mid];
    if (midNum == target) {
      // 收缩左侧边界, 向右继续搜索
      l = mid + 1;
    } else if (midNum < target) {
      // 更新搜索区间 [mid+1, h]
      l = mid + 1;
    } else if (midNum > target) {
      // 更新搜索区间 [l, mid-1]
      h = mid - 1;
    }
  }
  // 没有找到的情况的特殊处理
  if (h < 0 || nums[h] != target) {
    return -1;
  }
  return h;
}

我们再看下如何用搜索左闭右开的形式下的右侧边界二分搜索, 持续搜索的边界是 [l, h):
1.如何收缩左侧的边界? 我们的搜索区间是 [l, h), 因此收缩左侧边界的操作为 mid 直接+1, 也就是l = mid + 1
2.这时候我们二分的搜索区间 [l, h) 分别是 [mid+1, h) 和 [l, mid)
3.在判断没有找到的情况的特殊处理, 需要判断的是l-1的是否<0 或者 nums[l-1] != target, 且返回的是 l-1, 这是为什么?
4.我们在判定 nums[mid] == target 的时收缩左侧边界用的是 l = mid+1 进行左侧边界收缩, 也就是说 mid = l-1 因为我们对l的更新必须是 l = mid+1, 在 while 结束时, nums[l] 不一定等于 target 了, 而 nums[l-1] 可能等于 target
5.while终止的条件是 (l == h), 所以找到最终的结果返回 h-1, 或者判断没有找到的情况将 l-1 换成 h-1 是一样的

int binarySearchHigherBound(vector<int>& nums, int target) {
  int l = 0;
  int h = nums.size(); 
  while (l < h) {
    int mid = l + (h - l) / 2;
    int midNum = nums[mid];
    if (midNum == target) {
      // 收缩左侧边界, 向右继续搜索
      l = mid + 1;
    } else if (midNum < target) {
      // 搜索区间变为[mid+1, h)
      l = mid + 1;
    } else if (midNum > target) {
      // 搜索区间变为[l, mid)
      h = mid;
    }
  }
  // 没有找到的情况的特殊处理
  if (l-1 < 0 || nums[l-1] != target) {
    return -1;
  }
  return l - 1;
}

测试代码, 在找不到的情况先不采用返回 -1 这种设定, 打出来最后的值

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;

int binarySearchLowerBound(vector<int>& nums, int target) {
  int l = 0;
  int h = nums.size() - 1; 
  while (l <= h) {
    int mid = l + (h - l) / 2;
    int midNum = nums[mid];
    if (midNum == target) {
      // 持续收缩右侧边界
      h = mid - 1;
    } else if (midNum < target) {
      // 更新搜索区间 [mid+1, h]
      l = mid + 1;
    } else if (midNum > target) {
      // 更新搜索区间 [l, mid-1]
      h = mid - 1;
    }
  }
  return l;
}

int binarySearchHigherBound(vector<int>& nums, int target) {
  int l = 0;
  int h = nums.size() - 1; 
  while (l <= h) {
    int mid = l + (h - l) / 2;
    int midNum = nums[mid];
    if (midNum == target) {
      // 收缩左侧边界, 向右继续搜索
      l = mid + 1;
    } else if (midNum < target) {
      // 搜索区间变为[mid+1, h]
      l = mid + 1;
    } else if (midNum > target) {
      // 搜索区间变为[l, mid-1]
      h = mid - 1;
    }
  }
  return h;
}

int main() {
  vector<int> c{0,1,2,3,4,5,5,5,6,7,8,9,10};
    std::cout << "target=8, lower_pos=" << binarySearchLowerBound(c, 8) << std::endl;
    std::cout << "target=5, lower_pos=" << binarySearchLowerBound(c, 5) << std::endl;
    std::cout << "target=11, lower_pos=" << binarySearchLowerBound(c, 11) << std::endl;
    std::cout << "target=0, lower_pos=" << binarySearchLowerBound(c, 0) << std::endl;

    std::cout << "target=8, higher_pos=" << binarySearchHigherBound(c, 8) << std::endl;
    std::cout << "target=5, higher_pos=" << binarySearchHigherBound(c, 5) << std::endl;
    std::cout << "target=11, higher_pos=" << binarySearchHigherBound(c, 11) << std::endl;
    std::cout << "target=0, higher_pos=" << binarySearchHigherBound(c, 0) << std::endl;

  std::cout << std::endl;
  c = vector<int>{0,1,2,3,4,6,7,8,9,10};
    std::cout << "target=5, lower_pos=" << binarySearchLowerBound(c, 5) << std::endl;
    std::cout << "target=11, lower_pos=" << binarySearchLowerBound(c, 11) << std::endl;

    std::cout << "target=5, higher_pos=" << binarySearchHigherBound(c, 5) << std::endl;
    std::cout << "target=11, higher_pos=" << binarySearchHigherBound(c, 11) << std::endl;
  return 0;
}

输出结果

target=8, lower_pos=10
target=5, lower_pos=5
target=11, lower_pos=13
target=0, lower_pos=0
target=8, higher_pos=10
target=5, higher_pos=7
target=11, higher_pos=12
target=0, higher_pos=0

target=5, lower_pos=5
target=11, lower_pos=10
target=5, higher_pos=4
target=11, higher_pos=9

二分搜索的在 CPP 中的 api

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  vector<int> nums = {4,10,11,30,30,30,69,70,96,100};
  int t0 = 70;
  int t1 = 101;
  // binary_search 返回的是有没有找到, 找到了返回1, 否则返回0
  int b0 = binary_search(nums.begin(), nums.end(), t0);
  int b1 = binary_search(nums.begin(), nums.end(), t1);
  cout << "b0:" << b0 << endl;
  cout << "b1:" << b1 << endl;

  int t2 = 30;
  int t3 = 100;
  // lower_bound 二分搜索的是左边边界, 否则返回 nums.end()
  // lower_bound 二分搜索的是左边边界, 否则返回 nums.end()
  auto l = lower_bound(nums.begin(), nums.end(), t2);
  // upper_bound 二分搜索的第一个严格大于 target 的元素, 否则返回 nums.end()
  auto u = upper_bound(nums.begin(), nums.end(), t2);

  if (l != nums.end() && *l == t2)  {
    cout << "find t2 lower_bound, t2.index = " << l - nums.begin() << endl;
  } else {
    cout << "no find" << endl;
  }
  if (u != nums.end())  {
    cout << "find t2 upper_bound, first greater than t2 = " << *u << endl;
  } else {
    cout << "no find" << endl;
  }

  auto u3 = upper_bound(nums.begin(), nums.end(), t3);
  if (u3 != nums.end())  {
    cout << "find t3 upper_bound, first greater than t3 = " << *u3 << endl;
  } else {
    cout << "no element greater than t3" << endl;
  }
  return 0;
}

标准数组中的二分搜索

34.在排序数组中搜索元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：输入：nums = [], target = 0 输出：[-1,-1]

分析:
1.题意为搜索左侧边界和右侧边界的二分搜索

class Solution {
 public:
  int binarySearchLowerBound(vector<int>& nums, int target) {
    int l = 0;
    int h = nums.size() - 1; 
    while (l <= h) {
      int mid = l + (h - l) / 2;
      int midNum = nums[mid];
      if (midNum == target) {
        // 收缩右侧边界, 向左继续搜索
        h = mid - 1;
      } else if (midNum < target) {
        // 搜索区间变为[mid+1, h]
        l = mid + 1;
      } else if (midNum > target) {
        // 搜索区间变为[l, mid-1]
        h = mid - 1;
      }
    }
    // 没有找到的情况的特殊处理
    if (l >= nums.size() || nums[l] != target) {
      return -1;
    }
    return l;
  }
  int binarySearchHigherBound(vector<int>& nums, int target) {
    int l = 0;
    int h = nums.size() - 1; 
    while (l <= h) {
      int mid = l + (h - l) / 2;
      int midNum = nums[mid];
      if (midNum == target) {
        // 收缩左侧边界, 向右继续搜索
        l = mid + 1;
      } else if (midNum < target) {
        // 搜索区间变为[mid+1, h]
        l = mid + 1;
      } else if (midNum > target) {
        // 搜索区间变为[l, mid-1]
        h = mid - 1;
      }
    }
    // 没有找到的情况的特殊处理
    if (h < 0 || nums[h] != target) {
      return -1;
    }
    return h;
  }
  vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> ans = {binarySearchLowerBound(nums, target), binarySearchHigherBound(nums, target)};
    return ans;
  }
};

704.二分搜索

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例 2: 输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

分析:
1.基础的二分搜索实现, 可以用闭区间搜索和左闭右开搜索两种方法

class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int l = 0;
    int h = nums.size() - 1;
    while (l <= h) {
      int mid = l + (h - l) / 2;
      int midNum = nums[mid];
      if (midNum == target) {
        return mid;
      } else if (midNum < target) {
        l = mid + 1;
      } else if (midNum > target) {
        h = mid - 1;
      }
    }
    return -1;
  }
};

35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2

示例 2: 输入: nums = [1,3,5,6], target = 2 输出: 1

示例 3: 输入: nums = [1,3,5,6], target = 7 输出: 4

分析:
1.插入位置相当于找第 1 个 >= target 的位置

class Solution {
 public:
  int searchInsert(vector<int>& nums, int target) {
    int l = 0;
    int h = nums.size() - 1;
    // target <= nums[pos] || nums[pos-1] < target
    // 两种情况找到的都是左侧边界
    while (l <= h) {
      int mid = l + (h - l) / 2;
      if (nums[mid] == target) {
        return mid;
      } else if (nums[mid] < target) {
        l = mid + 1;
      } else if (nums[mid] > target) {
        h = mid - 1;
      }
    }
    return l;
  }
};

---

转载请注明来源, from goldandrabbit.github.io