前言二分查找属于最恶心细节最多最容易写出死循环的算法。但是同是也是很简单的算法因为有模板而且很容易学会。主要应用与数组有序或者无序(有规律)的情况下。模板主要是朴素二分模板、查找左边界的二分模板、查找右边界的二分模板。1.二分查找题目链接704. 二分查找 - 力扣LeetCode思路图这道题就是一道朴素的二分模板。代码实现class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size()-1; while(left right) { //int mid (right left) / 2; int mid left (right - left 1) / 2; //防溢出 cout left : left - right : right endl; if(nums[mid] target) left mid 1; else if(nums[mid] target) right mid - 1; else return mid; } return -1; } };时空分析时间复杂度时O(logn)底数是2。空间复杂度为O(1)几个变量即可。2.在排序数组中查找第一个和最后一个位置题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode思路图这道题相当于是查找左边界和右边界的结合情况还是有点复杂主要细节太多。需要分别分析很容易写出死循环建议每种情况先自己推荐一遍。上图解释了为什么需要有两个中点公式左端点和右端点是不一样的否则就会死循环。代码实现class Solution { public: vectorint searchRange(vectorint nums, int target) { int n nums.size(); if(!n) return {-1,-1}; int left 0, right n - 1, mid 0; vectorint ret; // 查找左端点 while (left right) { // left right 就是结果 mid left (right - left) / 2; if(nums[mid] target) left mid 1; else right mid; } if(nums[left] ! target) return {-1,-1}; ret.push_back(left); //查找右端点 left 0,right n - 1; while(left right) { mid left (right - left 1) / 2; if(nums[mid] target) right mid - 1; else left mid; } ret.push_back(left); return ret; } };时空分析时间复杂度是O(logn)两个二分查找。空间复杂度为O(1)虽然定义了一个vector但是只会消耗两个整型。3.x的平方根题目链接69. x 的平方根 - 力扣LeetCode思路图从1遍历到n使用二分查找注意循环条件和mid的取值公式不是固定的。需具体问题具体分析。只要不会造成死循环即可。像这里中点公式就只能使用另一个否则就会死循环。做多了你就会发现其实就这点套路。循环条件只能是left right当leftright时就是该值应该退出。代码实现class Solution { public: int mySqrt(int x) { if (!x) return x; int left 1,right x; while(left right) { //必须1防止死循环 int mid left (right - left 1) / 2; // cout left : left - right : right endl; if((long)mid*mid x) right mid - 1; else left mid; } return left; } };时空分析时间复杂度为O(logN)一次二分查找。空间复杂度为O(1)。4.搜索插入位置题目链接LCR 068. 搜索插入位置 - 力扣LeetCode思路图循环条件和中点处理需要特判一下别死循环。其他就没什么细节问题了。自己去推演一遍就很清楚了。代码实现class Solution { public: int searchInsert(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 right mid; } if(nums[left] target) return left; else return left 1; } };时空分析时间复杂度为O(logN)一次二分查找完成。空间复杂度为O(1)几个变量即可。5.山脉数组的峰顶索引题目链接852. 山脉数组的峰顶索引 - 力扣LeetCode思路图题目说了一定存在山脉数组所以不用讨论不存在的情况。当二分查找完毕数组应该是一个山顶的形状山顶就是我们要找的结果也就是left right的时候。其次在讨论一下中点公式基本思路就出来了。代码实现class Solution { public: int peakIndexInMountainArray(vectorint arr) { int left 0, right arr.size() - 1; while(left right) { int mid left (right - left) / 2; cout left : left - right : right endl; if(arr[mid] arr[mid1]) right mid; else left mid 1; } return left; } };时空分析时间复杂度为O(logN)一次二分查找即可。空间复杂度为O(1)。
前言二分查找属于最恶心细节最多最容易写出死循环的算法。但是同是也是很简单的算法因为有模板而且很容易学会。主要应用与数组有序或者无序(有规律)的情况下。模板主要是朴素二分模板、查找左边界的二分模板、查找右边界的二分模板。1.二分查找题目链接704. 二分查找 - 力扣LeetCode思路图这道题就是一道朴素的二分模板。代码实现class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size()-1; while(left right) { //int mid (right left) / 2; int mid left (right - left 1) / 2; //防溢出 cout left : left - right : right endl; if(nums[mid] target) left mid 1; else if(nums[mid] target) right mid - 1; else return mid; } return -1; } };时空分析时间复杂度时O(logn)底数是2。空间复杂度为O(1)几个变量即可。2.在排序数组中查找第一个和最后一个位置题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode思路图这道题相当于是查找左边界和右边界的结合情况还是有点复杂主要细节太多。需要分别分析很容易写出死循环建议每种情况先自己推荐一遍。上图解释了为什么需要有两个中点公式左端点和右端点是不一样的否则就会死循环。代码实现class Solution { public: vectorint searchRange(vectorint nums, int target) { int n nums.size(); if(!n) return {-1,-1}; int left 0, right n - 1, mid 0; vectorint ret; // 查找左端点 while (left right) { // left right 就是结果 mid left (right - left) / 2; if(nums[mid] target) left mid 1; else right mid; } if(nums[left] ! target) return {-1,-1}; ret.push_back(left); //查找右端点 left 0,right n - 1; while(left right) { mid left (right - left 1) / 2; if(nums[mid] target) right mid - 1; else left mid; } ret.push_back(left); return ret; } };时空分析时间复杂度是O(logn)两个二分查找。空间复杂度为O(1)虽然定义了一个vector但是只会消耗两个整型。3.x的平方根题目链接69. x 的平方根 - 力扣LeetCode思路图从1遍历到n使用二分查找注意循环条件和mid的取值公式不是固定的。需具体问题具体分析。只要不会造成死循环即可。像这里中点公式就只能使用另一个否则就会死循环。做多了你就会发现其实就这点套路。循环条件只能是left right当leftright时就是该值应该退出。代码实现class Solution { public: int mySqrt(int x) { if (!x) return x; int left 1,right x; while(left right) { //必须1防止死循环 int mid left (right - left 1) / 2; // cout left : left - right : right endl; if((long)mid*mid x) right mid - 1; else left mid; } return left; } };时空分析时间复杂度为O(logN)一次二分查找。空间复杂度为O(1)。4.搜索插入位置题目链接LCR 068. 搜索插入位置 - 力扣LeetCode思路图循环条件和中点处理需要特判一下别死循环。其他就没什么细节问题了。自己去推演一遍就很清楚了。代码实现class Solution { public: int searchInsert(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 right mid; } if(nums[left] target) return left; else return left 1; } };时空分析时间复杂度为O(logN)一次二分查找完成。空间复杂度为O(1)几个变量即可。5.山脉数组的峰顶索引题目链接852. 山脉数组的峰顶索引 - 力扣LeetCode思路图题目说了一定存在山脉数组所以不用讨论不存在的情况。当二分查找完毕数组应该是一个山顶的形状山顶就是我们要找的结果也就是left right的时候。其次在讨论一下中点公式基本思路就出来了。代码实现class Solution { public: int peakIndexInMountainArray(vectorint arr) { int left 0, right arr.size() - 1; while(left right) { int mid left (right - left) / 2; cout left : left - right : right endl; if(arr[mid] arr[mid1]) right mid; else left mid 1; } return left; } };时空分析时间复杂度为O(logN)一次二分查找即可。空间复杂度为O(1)。
)
