二分查找创新性总结

• 704.二分查找
• 35.搜索插入位置
• 69.x 的平方根
• 367.有效的完全平方数
• 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 };}
};