在线网站建设哪家便宜,网站pv uv 多少算好站,wordpress wp trim,备案网站注意事项文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;二分查找闭区间左闭右开区间开区间总结 知识总结写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c… 文章目录 写在前面Tag题目来源题目解读解题思路方法一二分查找闭区间左闭右开区间开区间总结 知识总结写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【二分查找】【数组】 题目来源
35. 搜索插入位置 题目解读
其实就是找出数组中大于等于 target 的最小值所在的位置。 解题思路
在数组中找到第一个大于或者等于 target 值的所在位置数据量不大约为 O ( 1 0 4 ) O(10^4) O(104)可以一次遍历查找也开始使用二分查找来解决。题目要求使用时间复杂度为 O ( l o g n ) O(logn) O(logn) 的算法那就只能使用二分法来解答了。
方法一二分查找
二分查找是一种高效的搜索算法在有序数组的指定区间内根据要求搜索元素根据当前区间的中点的搜索情况缩短区间每次搜索都会缩短一半的区间时间复杂度为 O ( l o g n ) O(logn) O(logn) n n n 为有序数组的长度。
二分查找根据区间的开闭分为以下三种情况
闭区间左闭右开区间开区间。
二分查找的区间无论是哪种闭合形式要关注的 问题 始终是三个
一是何时退出循环二是表示左、右区间的左、右指针如何移动三是返回什么。
以下将针对三种二分法的三个问题分别进行分析。
闭区间
闭区间表示搜索的区间是闭合的初始的闭合区间为 [0, n-1]即指针指向 l 0, r n-1。
何时退出循环
当区间为空的时候退出 while 循环何时区间为空
当 l r 时指针 l 位于指针 r 右侧已经构不成区间了退出 while 循环。
因此此时的 while 循环条件为 l r。
左、右指针如何移动
在闭区间情况下如果 nums[mid] target说明 target 的值在右侧区间于是只需要更新左指针 l mid 1否则nums[mid] target说明 mid 及其之后的位置都是确定大于 target 的这时候需要更新右指针 r mid - 1 来判断左区间内的数。
返回什么
退出循环后r 指向的位置为 l 指向位置左侧的第一个位置最后返回 l 或者 r 1。
实现代码
class Solution {
public:int searchInsert(vectorint nums, int target) {int n nums.size();int l 0, r n - 1;while (l r) { // 区间为空退出循环int mid l ((r - l) 1);if (nums[mid] target) {l mid 1;}else {r mid - 1;}}return l; // 等价于 return r1}
};左闭右开区间
左闭右开区间表示搜索的区间是左闭右开的初始的指针指向为 l 0, r n。
何时退出循环
当区间为空的时候退出 while何时区间为空
因为 r 指针是取不到的所以当 l r 时区间为空因为实际的区间左端点为 l右端点为 r构不成区间退出 while 循环。
此时的 while 循环条件为 l r。
左、右指针如何移动
在左闭右开区间情况下如果 nums[mid] target说明 target 的值在右侧区间于是只需要更新左指针 l mid 1否则nums[mid] target说明 mid 及其之后的位置都是确定大于 target 的这时候需要更新右指针 r mid 来判断左区间即 [l, mid-1] 中的数。
返回什么
退出循环后r 和 l 指向的是同一个位置最后返回 l 或者 r。
实现代码
class Solution {
public:int searchInsert(vectorint nums, int target) {int n nums.size();int l 0, r n;while (l r) { // 区间为空退出循环int mid l ((r - l) 1);if (nums[mid] target) {l mid 1;}else {r mid;}}return l; // 等价于 return r}
};开区间
开区间表示搜索的区间两边都是开的初始的指针指向为 l -1, r n。
何时退出循环
当区间为空的时候退出 while何时区间为空
因为 l 和 r 指针指向的值是取不到的所以当 l 1 r 时(l, r) 表示的区间为空退出 while 循环。
此时的 while 循环条件为 l 1 r。
左、右指针如何移动
在开区间情况下如果 nums[mid] target说明 target 的值在右侧区间于是只需要更新左指针 l mid因为左区间是开的实际的区间是 mid 1否则nums[mid] target说明 mid 及其之后的位置都是确定大于 target 的这时候需要更新右指针 r mid 来判断左区间即 [l, mid - 1] 中的数。
返回什么
退出循环后l 指向的位置位于 r 指向位置的左侧最后返回 r 或者 l1。
总结
无论是哪种区间闭合形式关注的始终是何时退出while循环、左右指针如何更新以及最后返回什么这三个问题。
需要注意的移动指针一定要保证原来区间的闭合与否原来区间是闭合的更新后的指针指向的依旧是闭合的区间原来区间是开的更新后的指针指向的依旧是开的区间。
以上三种形式可以挑选一种自己熟悉的形式记忆并记住这是解决在有序数组中查找大于等于指定值的代码。 知识总结
在有序数组中查找大于等于指定值的最小位置的二分查找方法是十分经典该方法已经被封装成了一个函数 lower_bound()该方法之所以是经典是因为其他类型的查找都可以通过它来完成
在有序数组中查找大于等于指定值的最小位置这就不赘述了在有序数组中查找大于指定值 x 的最小位置本题及以下等价转换仅限于整数数组。此时可以等价转化为 “在有序数组中查找大于等于指定值 x1 的最小位置”在有序数组中查找小于指定值 x 的最大位置可以等价转化为 “在有序数组中查找大于等于指定值 x 的最小位置” 减 1在有序数组中查找小于等于指定值 x 的最大位置可以等价转化为 “在有序数组中查找大于等于指定值 x1 的最小位置” 减 1。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
