西宁网站制作哪家好,园林景观设计公司简介范文,wordpress模板添加主题,输入法网站设计二分模板一共有两个#xff0c;分别适用于不同情况。 算法思路#xff1a;假设目标值在闭区间[l, r]中#xff0c; 每次将区间长度缩小一半#xff0c;当l r时#xff0c;我们就找到了目标值。
* 其中mid需要在while内部进行更新
* 最小R#xff0c;最大L , R来加分别适用于不同情况。 算法思路假设目标值在闭区间[l, r]中 每次将区间长度缩小一半当l r时我们就找到了目标值。
* 其中mid需要在while内部进行更新
* 最小R最大L , R来加L来减 C 代码模板
// 整数二分算法模板bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid 1, r]时使用
int bsearch_1(int l, int r)
{while (l r){int mid l r 1;if (check(mid)) r mid; // check()判断mid是否满足当前条件最小值性质else l mid 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
int bsearch_2(int l, int r)
{while (l r){int mid l r 1 1;if (check(mid)) l mid; // check()判断mid是否满足当前条件最大值性质else r mid - 1;}return l;
}69. x 的平方根
思路使用二分法因为是向下取整即满足向下取整的最大性质
class Solution {
public:int mySqrt(int x) {int l 0, r x;while(l r){long mid (l r 1ll) 1;if(mid * mid x) l mid;else r mid - 1;}return l;}
};
33. 搜索旋转排序数组
思路使用两段二分
class Solution {
public:int search(vectorint nums, int target) {if (nums.empty()) return -1;int l 0, r nums.size() - 1;while (l r) {int mid l r 1 1;if (nums[mid] nums[0]) l mid;else r mid - 1;}if (target nums[0]) l 0;else l r 1, r nums.size() - 1;while (l r) {int mid l r 1;if (nums[mid] target) r mid;else l mid 1;}if (nums[r] target) return r;return -1;}
};
34. 在排序数组中查找元素的第一个和最后一个位置
解题思路使用二分法二分出左右区间两个满足的位置然后返回结果
class Solution {
public:vectorint searchRange(vectorint nums, int target) {if(nums.empty())return {-1,-1};int l 0 , r nums.size() - 1;while( l r){int mid (l r) 1;if(nums[mid]target)r mid;else l mid 1;}if(nums[r] ! target) return{-1,-1};int start r;l 0,r nums.size() - 1;while(l r){int mid (l r 1) 1 ;if(nums[mid] target) l mid;else r mid - 1;}int end r;return {start , end};}
};
35. 搜索插入位置
解题思路二分找到寻找满足性质的最小部分。
class Solution {
public:int searchInsert(vectorint nums, int target) {if(nums.empty())return 0; int l 0, r nums.size();while(l r){int mid l r 1;//需要找到的x和target的关系是x是target右侧最小的一个if(nums[mid]target)r mid;else l mid 1;}return l;}
};
