一个网站页面设计多少钱,做预算查价格的网站是哪个,wordpress1003无标题,wordpress菜单小工具个人主页#xff1a;敲上瘾-CSDN博客 个人专栏#xff1a;游戏、数据结构、c语言基础、c学习、算法 本章我们来学习的是二分查找算法#xff0c;二分算法的应用非常广泛#xff0c;不仅限于数组查找#xff0c;还可以用于解决各种搜索问题、查找极值问题等。在数据结构和算… 个人主页敲上瘾-CSDN博客 个人专栏游戏、数据结构、c语言基础、c学习、算法 本章我们来学习的是二分查找算法二分算法的应用非常广泛不仅限于数组查找还可以用于解决各种搜索问题、查找极值问题等。在数据结构和算法中它是基础且重要的算法之一。
接下来我准备了三个题来引出并学习该算法最后来做总结。
目录
一、二分查找
1.题目解析
2.算法原理
3.代码编写
二、查找元素的首末位置
1.题目解析
2.算法原理
3.代码编写
三、寻找峰值
1.题目解析
2.算法原理
3.代码编写
四、总结 一、二分查找
1.题目解析 该题目要求是给一个元素target然后在升序数组nums中找到该元素的下标若不存在则返回-1。题目要求简单易懂就不再多讲这里要注意两个点(1)、数组是升序的。(2)、需要返回的是元素下标。
2.算法原理 对于该题最容易想到的解法就是把数组从头到尾遍历一遍时间复杂度为O(N)。 解法二因为这个数组是有序的所以我们可以用二分的思想首先使用三个指针这里指的是数组的下标leftrightmid其中left和right维护一段区间把目标值锁定到[leftright]区间内。mid表示区间的中心下标把区间一分为二。 接下来锁定target的位置如果target小于mid下标指向的元素那么因为数组是升序所以target一定在区间[leftmid]中即right更新为mid然后更新mid midleft(right-left)/2 。 如果target大于mid指向元素那么target一定在区间[midright]中即把left更新为mid然后更新mid。重复操作直到leftright。
如下 该算法的时间复杂度为logN证明如下 3.代码编写
class Solution
{
public:int search(vectorint nums, int target){int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target) rightmid-1;else if(nums[mid]target) leftmid1;else return mid;}return -1;}
};
二、查找元素的首末位置
1.题目解析 该题的题目要求与上一题类似都是在升序数组中查找元素不过该题查找的是元素第一次出现的位置和最后一次出现的位置。这里还要求时间复杂度为O(logN)这里就很明显地提示了该题要使用二分算法。
2.算法原理 同样的此题可以使用暴力枚举来解决不过时间复杂度为O(N)根据上题的经验这里我们还是考虑使用二分法。不过也很容易发现把上面的算法原模原样搬过来是解决不了该道题的我们只能找到target元素的是无法锁定它第一次出现的位置和最后一次出现的位置。我们可以用以下解法 左边界查找 当mid指向的元素为target的时候不用返回而是让right更新为midmid指向元素大于target时同样更新right为mid即可以合并为 if(nums[mid]target) rightmid; 当mid指向元素小于target时left更新为mid1重复该操作就可以把数组右边的target忽略锁定最左边的target。这里做循环的时候需要注意循环条件不能是leftrigth如果是leftright就可能使mid一直赋值给right从而进入死循环所以我们使用leftright。 右边界查找 当mid指向的元素为target的时候不用返回而是让left更新为midmid指向元素小于target时同样更新left为mid即可以合并为 if(nums[mid]target) leftmid; 当mid指向元素大于target时right更新为mid-1重复该操作就可以把数组左边的target忽略锁定最右边的target。这里做循环的时候同样需要注意循环条件只能是leftrigth。 注意当元素只有两个时使用midleft(right-left)/2计算的mid就是第一个元素那么也就是midleft如果mid指向的元素为target时把mid赋值给left即leftmid相当于什么也没干程序同样会进入死循环。所以我们使用midleft(right-left1)/2计算mid。 以上的两个查找法几乎可以解决所有的二分算法题可以作为一个模板记忆在总结部分我会给出模板。
3.代码编写
class Solution
{
public:vectorint searchRange(vectorint nums, int target) {if(nums.size()0) return {-1,-1};int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target) rightmid;else leftmid1;}if(nums[left]!target) return {-1,-1};int nleft;rightnums.size()-1;while(leftright){int midleft(right-left1)/2;if(nums[mid]target) leftmid;else rightmid-1;}return {n,left};}
};
三、寻找峰值
1.题目解析 该题要求我们返回任意峰值比如把数组元素抽象成连续的数据如下 需要返回以上红圈部分的任意一点 也就是该元素至少要满足它左边的第一个元素和右边的第一个元素都要小于它。
注意题目给的信息nums[-1]和nums[n]为负无穷所以不要忽略以下情况 2.算法原理 这题同样可以使用暴力枚举时间复杂度为O(N)该解法就不再多讲。 这个题与上两个题有一个很大的区别是该数组并不是有序的但是没关系该题同样可以使用二分的思想注意很多人会误认为二分算法只能用在有序的数组中而事实并不局限于此只需要找到数据的二段性即可如该题我们可以这样 该方法也就是上一题的右边界查找当然也可以使用左边界查找的方法但用朴素的二分查找解决不了该题。
3.代码编写 class Solution
{
public:int findPeakElement(vectorint nums) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]nums[mid1]) rightmid;else leftmid1;}return left;}
};
四、总结
1、二分算法并不局限于数组有序只要找到数据的二段性即可使用二分算法。
2、二分算法模板 2.1.朴素二分模板 while(leftright)
{int midleft(right-left)/2;if(...) leftmid1;else if(...) rightmid-1;else ...
} 2.2.左边界查找模板 while(leftright)
{int midleft(right-left)/2;if(...) leftmid1;else rightmid;
} 2.3.右边界查找模板 while(leftright)
{int midleft(right-left1)/2;if(...) leftmid;else rightmid-1;
}
