二分查找创新性总结

• LeetCode题目
  • 704.二分查找
  • 35.搜索插入位置
  • 69.x 的平方根
  • 367.有效的完全平方数
  • 34.在排序数组中查找元素的第一个和最后一个位置
• 二分查找适用范围
  • 可随机访问的数据结构
  • 数据已经有序
  • 要查找的值只有一个
• 上述的前四题都可直接使用二分查找，第五题要求查找上限和下限，可以通过两个二分查找实现
• 二分查找易错点
  • 容易导致重复递归
  • 边界条件不容易确定
• 本文的创新在于：将二分查找作为一个限定范围的工具，不要求二分查找直接给出结果，而是将结果范围限制在三个值中，然后对三个值进行判断，从而无需考虑边界条件，大大降低思考难度
• 题目讲解：以35和34为例
  • 35.搜索插入位置

  class Solution {
  private:int target;// 下列写法用于：在nums中查找最接近target的下标// 通用写法，无需考虑边界条件int bi_search(int left_index, int right_index, vector<int>& nums){// 递归中止条件if (left_index >= right_index)return right_index;auto mid_index = ((right_index - left_index) >> 1) + left_index;auto mid = nums[mid_index];// mid+1和mid-1保证不会重复递归if (mid < target)return bi_search(mid_index + 1, right_index, nums);else if (mid > target)return bi_search(left_index, mid_index - 1, nums);return mid_index;}int check(vector<int>& candidates, vector<int>& nums){auto size = nums.size();int ans = -1;for (auto& candidate : candidates) {// 必须先检查下标是否合法// 由于限制了下标必须合法，所以非法下标需要作为corner case处理if (candidate >= 0 && candidate <= (size - 1)) {// 按照顺序对ans进行更新// 若不符合条件，则不更新，因此下标的顺序很关键if (nums[candidate] >= target)ans = candidate;}}return ans;}public:int searchInsert(vector<int>& nums, int _target){target = _target;auto size = nums.size();if (0 == size)return 0;if (1 == size) {if (nums[0] >= target)return 0;else if (nums[0] < target)return 1;}// 关键步骤：保证要查找的下标一定在[0, size-1]范围内，即合法化// 因为本方法只能查找合法的下标if (nums[0] >= target)return 0;if (nums[size - 1] < target)return size;auto mid_index = bi_search(0, size - 1, nums);// 二分查找保证了最接近target的下标一定在// mid_index + 1, mid_index, mid_index - 1三个其中之一// 下标的顺序很关键：由于是查找大于等于target的下标，所以要从大到小更新vector<int> candidates { mid_index + 1, mid_index, mid_index - 1 };// 检查这三个下标，得到结果auto ans = check(candidates, nums);// 若三个小标都不符合条件，则ans=-1// 实际上已经排除了非法下标，所以无需判断// if (-1 == ans)//     return size;return ans;}
  };
  

  • 34.在排序数组中查找元素的第一个和最后一个位置

  class Solution {
  private:int target;// nums中查找target的下限的下标int bi_search_lower(int left_index, int right_index, vector<int>& nums){if (left_index >= right_index)return right_index;auto mid_index = ((right_index - left_index) >> 1) + left_index;auto mid = nums[mid_index];if (mid >= target)return bi_search_lower(left_index, mid_index - 1, nums);elsereturn bi_search_lower(mid_index + 1, right_index, nums);}// nums中查找target的上限的下标int bi_search_upper(int left_index, int right_index, vector<int>& nums){if (left_index >= right_index)return right_index;auto mid_index = ((right_index - left_index) >> 1) + left_index;auto mid = nums[mid_index];if (mid > target)return bi_search_upper(left_index, mid_index - 1, nums);elsereturn bi_search_upper(mid_index + 1, right_index, nums);}int check(vector<int>& candidates, vector<int>& nums){auto size = nums.size();int ans = -1;for (auto& candidate : candidates) {// 先判断合法性if (candidate >= 0 && candidate <= (size - 1)) {// 再更新ansif (nums[candidate] == target)ans = candidate;}}return ans;}public:vector<int> searchRange(vector<int>& nums, int _target){target = _target;auto size = nums.size();if (0 == size)return { -1, -1 };if (1 == size) {if (nums[0] == target)return { 0, 0 };return { -1, -1 };}// 保证要查找的下标是合法的if (nums[0] > target)return { -1, -1 };if (nums[size - 1] < target)return { -1, -1 };auto mid_index = bi_search_lower(0, size - 1, nums);// 找下限，要从大到小更新vector<int> candidates = { mid_index + 1, mid_index, mid_index - 1 };auto lower = check(candidates, nums);// 要处理查找失败的情况if (-1 == lower)return { -1, -1 };mid_index = bi_search_upper(0, size - 1, nums);// 找上限，要从小到大更新candidates[0] = mid_index - 1;candidates[1] = mid_index;candidates[2] = mid_index + 1;auto upper = check(candidates, nums);// 一定要处理查找失败的情况if (-1 == upper)return { -1, -1 };return { lower, upper };}
  };