二分我********二分查找的介绍二分查找的特点在二分查找中它是最恶心细节最多最容易写出死循环的算法但是只要我们把它弄清楚去理解最恶心就会变得最简单了学习中的侧重点1、算法原理使用二分查找不止可以在数组有序得情况去使用在我们理解的深刻那么我们也可以发现一些规律即使在数组无序中我们也可以去使用二分优化2、模板我们学习二分一定要去理解模板不要去死记硬背理解之后再去记忆才能发挥最大的功能二分查找模板一共有3个朴素的二分模板虽然比较简单但是它有一定的局限性左边界和右边界其实也算我们的万能模板开始学习一、二、三上链接704. 二分查找 - 力扣LeetCode一朴素的二分模板二分查找算法原理1.二分查找算法的本质是利用数组的有序性和二段性进行高效搜索。2.二段性通过比较中间元素将数组分成两个子数组根据比较结果舍去一部分继续在另一部分搜索。3.适用范围不仅限于有序数组只要满足二段性即可。二段性就是分半mid left (right - left)/2;例如在一堆数组我们要找target1、如果这个数组比5小的也就是1~4不是我们的目标值我们是不是可以舍去答案是的目标值在5~7的区间里2、继续搜是不是如果比5大的我们也不要呢答案是的3、在搜索如果mid target此时这个就是我们的答案可以直接返回了最后为什么可以不要这些值因为他不是我们需要的值呀人家要找5你搜6和7的区间有个屁用二分查找算法细节问题1.定义left和right指针初始化搜索区间。2.循环条件left right。3.在循环中计算中间元素的索引mid并与目标值进行比较。4.根据比较结果更新left或right指针缩小搜索区间。5.如果找到目标元素返回其索引如果未找到返回-1。class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while(left right) { int mid left (right - left) / 2;//防止溢出 if(nums[mid] target) left mid 1; else if(nums[mid] target) right mid - 1; else return mid; } return -1; } };mid为什么这样子写int left 2,000,000,000; // 20亿 int right 2,000,000,000; // 20亿 int mid (left right) / 2; // left right 40亿 ❌ 超过 int 最大值 21.47亿left 1,500,000,000 right 2,000,000,000 right - left 500,000,000 // ✅ 差值很小不会溢出 mid 1,500,000,000 250,000,000 1,750,000,000 // ✅ 正确34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode二查找左边界的二分模板我们找7第一个出现的7为什么r要等于mid这仅适用于arr[mid] target的情况mid 值已大于 targetmid 及其右边都不可能等于 target。但如果arr[mid] targetmid 可能是答案不能rmid-1而应rmid保留 mid。为什么l要等于mid1如果arr[mid] target整个[l, mid]区间都小于 target不可能有答案所以应l mid1排除。如果arr[mid] target答案可能在[l, mid]此时不是lmid而是rmid向左收缩。三查找右边界的二分模板同理lmidarr[mid] targetmid 及其左边都可能 ≤ target但我们想要最右边的所以答案可能在[mid, r]区间因为 mid 可能就是答案也可能右边还有。此时应保留 mid收缩左边界l mid。rmidarr[mid] targetmid 的值已经大于 target那么 mid 及其右边都肯定不是答案直接排除r mid - 1细节讨论循环条件left right √当left right的时候就是最终结果如果判断容易造成死循环中点位置①left (right - left) / 2→左中位数偏左②left (right - left 1) / 2→右中位数偏右看一个极端例子left0, right1。如果找最后一个逻辑是if (arr[mid] target) l mid;用公式①偏左mid0→l 0区间[0,1]没变死循环。用公式②偏右mid1→l 1区间变为[1,1]正常退出。如果找第一个逻辑是if (arr[mid] target) r mid;用公式②偏右mid1→r 1区间[0,1]没变死循环。用公式①偏左mid0→r 0区间变为[0,0]正常退出。题目ac代码class Solution { public: vectorint searchRange(vectorint nums, int target) { if(nums.size()0)return {-1,-1}; int begin0; // 1、找左端点 int l0,rnums.size()-1; while(lr) { int midl(r-l)/2; if(nums[mid]target) { lmid1; }else { rmid; } } if(nums[l] ! target) return {-1,-1}; else beginl; // 2、找右端点 l0,rnums.size()-1; while(lr) { int midl(r-l1)/2; if(nums[mid]target) { lmid; }else{ rmid-1; } } return {begin,r}; } };总结模板
