网站建设类论文,在人才网站做业务,北京新闻发布会,建设教育协会官方网站LeetCode题目 704.二分查找35.搜索插入位置69.x 的平方根367.有效的完全平方数34.在排序数组中查找元素的第一个和最后一个位置 二分查找适用范围 可随机访问的数据结构数据已经有序要查找的值只有一个 上述的前四题都可直接使用二分查找#xff0c;第五题要求查找上限和下限第五题要求查找上限和下限可以通过两个二分查找实现二分查找易错点 容易导致重复递归边界条件不容易确定 本文的创新在于将二分查找作为一个限定范围的工具不要求二分查找直接给出结果而是将结果范围限制在三个值中然后对三个值进行判断从而无需考虑边界条件大大降低思考难度题目讲解以35和34为例 35.搜索插入位置 class Solution {
private:int target;// 下列写法用于在nums中查找最接近target的下标// 通用写法无需考虑边界条件int bi_search(int left_index, int right_index, vectorint nums){// 递归中止条件if (left_index right_index)return right_index;auto mid_index ((right_index - left_index) 1) left_index;auto mid nums[mid_index];// mid1和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(vectorint candidates, vectorint 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(vectorint 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的下标所以要从大到小更新vectorint 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, vectorint 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, vectorint 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(vectorint candidates, vectorint 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:vectorint searchRange(vectorint 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);// 找下限要从大到小更新vectorint 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 };}
};
