当前位置:首页 > 力扣 > 征服力扣704题:三步掌握经典二分查找算法

征服力扣704题:三步掌握经典二分查找算法

2个月前 (05-21)

征服力扣704题:三步掌握经典二分查找算法 递归 二分查找 数组 算法 力扣 C++ 第1张

题目重解

我们面对的是算法领域最经典的二分查找问题:在一个已排序的整数数组中,快速定位目标值的位置。就像在一本按字母顺序排列的字典中查找单词,我们不需要逐页翻阅,而是通过不断折半的方式快速缩小搜索范围,这正是二分查找的精髓所在。


解题思路解析

递归实现二分查找:

‌基准情况1‌:当搜索范围缩小到单个元素时(l == r),直接比较该元素

‌基准情况2‌:当范围剩两个元素时(l+1 == r),分别比较这两个元素

‌递归过程‌:计算中间位置,根据中间值与目标值的关系决定向左或向右继续搜索

整个过程就像是在玩"猜数字"游戏,每次猜测都能排除一半的错误答案,直到找到正确答案或确认不存在。递归的终止条件和边界处理确保了搜索的正确性和完整性。


代码注释版

class Solution {
public:
    int binaryselect(vector<int> a, int num, int l, int r) {
        // 情况1:搜索范围缩小到单个元素
        if (l == r) {
            if (a[l] == num)
                return l;  // 找到目标
            else
                return -1; // 未找到
        }
        // 情况2:搜索范围剩两个元素
        if (l + 1 == r) {
            if (a[l] == num)
                return l;
            else if (a[r] == num)
                return r;
            else
                return -1;
        }
        // 计算中间位置
        int mid = (l + r) / 2;
        if (a[mid] == num)
            return mid;  // 直接命中
        else if (a[mid] < num)
            return binaryselect(a, num, mid + 1, r); // 向右半部分继续搜索
        else
            return binaryselect(a, num, l, mid - 1); // 向左半部分继续搜索
    }
    
    int search(vector<int>& nums, int target) {
        // 从整个数组范围开始搜索
        return binaryselect(nums, target, 0, nums.size() - 1);
    }
};


原创内容 转载请注明出处

分享给朋友:

相关文章

手搓顺序表类代码注释与详解:从零实现动态数组(新手教程)

一、简介和特点顺序表(Sequential List)是数据结构中基础的一种线性表,其特点是将数据元素存储在连续的内存空间中。通过数组实现,支持随机访问(即通过索引直接访问元素),适用于频繁随机读取的...

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

力扣3112题解法:带时间限制的最短路径问题解析(C++代码)

一、题目解读力扣3112题要求解决带时间限制的最短路径问题:给定一个有向图,节点具有消失时间,需计算从起点到各节点的最短路径,且路径总时间不能超过节点的消失时间。题目难点在于需在传统最短路径算法(如D...

2012年NOIP提高组「借教室」题目(P1083)解题思路与二分查找优化代码解析

2012年NOIP提高组「借教室」题目(P1083)解题思路与二分查找优化代码解析

一、题目解读本题为2012年NOIP提高组中的「借教室」问题(洛谷P1083),要求处理教室借用订单的分配问题。给定n天每天可用教室数量r和m个订单(订单包含需求教室数d、开始日期s、结束日期t),判...

【洛谷1184题解析】用C++高效解决地点匹配问题(附代码与解题思路)

【洛谷1184题解析】用C++高效解决地点匹配问题(附代码与解题思路)

一、题目解读洛谷1184题要求处理一组地点列表与行程记录,统计其中匹配的天数。题目难点在于高效处理带有空格的字符串输入,以及快速判断每日行程是否在高手可去地点集合中。需要兼顾输入格式解析与算法效率。二...

洛谷1220题解:动态规划与区间DP优化解法(附代码注释)

洛谷1220题解:动态规划与区间DP优化解法(附代码注释)

一、题目解读洛谷1220题要求计算在n个位置放置灯的情况下,通过关闭连续区间灯并移动至区间端点,使得总耗电量最小。需考虑灯的功率与位置差异,设计高效的算法求解最优策略。二、解题思路1. 动态规划 +...

牛客NC67题解:汉诺塔递归算法与解题步骤

牛客NC67题解:汉诺塔递归算法与解题步骤

一、题目解读牛客NC67题要求解决汉诺塔问题,这是一个经典的递归算法题目。题目给定整数n,代表汉诺塔中的盘子数量,需要输出将n个盘子从起始柱移动到目标柱的所有步骤。汉诺塔问题规则为:每次只能移动一个盘...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。