开源展示型网站,中国卫生人才网官网,安卓系统app,网页制作的原则是什么#x1f31f;快来参与讨论#x1f4ac;#xff0c;点赞#x1f44d;、收藏⭐、分享#x1f4e4;#xff0c;共创活力社区。 #x1f31f; 别再犹豫了#xff01;快来订阅我们的算法每日双题精讲专栏#xff0c;一起踏上算法学习的精彩之旅吧#x1f4aa; 在算法的… 快来参与讨论点赞、收藏⭐、分享共创活力社区。 别再犹豫了快来订阅我们的算法每日双题精讲专栏一起踏上算法学习的精彩之旅吧 在算法的学习之旅中二分查找是一种高效且经典的算法其应用场景广泛。今天我们将深入探讨如何运用二分查找来解决 “寻找旋转排序数组中的最小值” 以及趣味十足的 “点名” 问题。这两道题不仅能加深我们对二分查找的理解还能锻炼我们在不同场景下灵活运用算法的能力。 目录
一、寻找旋转排序数组中的最小值
题目描述
讲解算法原理
代码实现以 C 为例
复杂度分析
二、点名
题目描述
讲解算法原理
代码实现以 C 为例
复杂度分析 一、寻找旋转排序数组中的最小值
题目链接【力扣】
题目描述 讲解算法原理
对于这道题我们可以利用二分查找来优化时间复杂度。 初始化左指针 left 为 0右指针 right 为数组长度减 1。在循环过程中计算中间索引 mid left (right - left) / 2 。 比较 nums[mid] 与 nums[right] 的大小 如果 nums[mid] nums[right] 说明最小值在 mid 及其左边因为 mid 到 right 这一段是有序的最小值肯定不在这一段所以将 right 更新为 mid 。 如果 nums[mid] nums[right] 说明最小值在 mid 的右边因为 mid 及其左边这一段是有序的最小值不在这一段所以将 left 更新为 mid 1 。 当 left 等于 right 时循环结束此时 nums[left] 就是数组中的最小值。 代码实现以 C 为例
#include iostream
#include vectorusing namespace std;int findMin(vectorint nums) {int left 0, right nums.size() - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] nums[right]) {right mid;}else {left mid 1;}}return nums[left];
}
复杂度分析 时间复杂度每次循环都将搜索区间缩小一半所以时间复杂度为 其中 是数组的长度。相比遍历整个数组查找最小值的暴力解法时间复杂度为 效率大大提高。 空间复杂度只使用了常数级别的额外空间即几个指针变量所以空间复杂度为 。 二、点名 题目链接【力扣】
题目描述 讲解算法原理
这道题同样可以借助二分查找来高效解决。 初始化左指针 left 为 0右指针 right 为名单长度减 1。 在循环中计算中间索引 mid left (right - left) / 2 。 比较中间位置的学生名字与老师点的名字 如果相同直接返回 mid 。 如果中间位置的名字小于老师点的名字说明要找的名字在 mid 的右边将 left 更新为 mid 1 。 如果中间位置的名字大于老师点的名字说明要找的名字在 mid 的左边将 right 更新为 mid - 1 。 当 left 大于 right 时循环结束说明名单中没有该学生返回 -1 。 代码实现以 C 为例
#include iostream
#include vector
#include stringusing namespace std;int rollCall(vectorstring names, string target) {int left 0, right names.size() - 1;while (left right) {int mid left (right - left) / 2;if (names[mid] target) {return mid;}else if (names[mid] target) {left mid 1;}else {right mid - 1;}}return -1;
}
复杂度分析 时间复杂度每次迭代都能将搜索区间缩小一半时间复杂度为 其中 是名单中学生的数量。相比逐个遍历名单查找学生的暴力解法时间复杂度为 效率大幅提升。 空间复杂度只使用了常数级别的额外空间如几个指针变量所以空间复杂度为 。 通过对这两道题目的学习我们对二分查找算法的理解和应用能力又上了一个新台阶。在今后遇到类似问题时要学会灵活运用二分查找来优化代码的时间复杂度。
如果大家在学习过程中有任何疑问或者想法欢迎在评论区交流分享。后续我还会带来更多精彩的算法内容记得关注哦
