202406261021_二分查找2
- ✏随笔
- 34. 在排序数组中查找元素的第一个和最后一个元素
- 代码
- 总结
- 69. x的平方根
- 代码
- 总结
- 367. 有效的完全平方数
- 代码
- 总结
(Weather::上海 ⛅多云,13~23℃ 良 清风徐徐🌘)
✏随笔
34. 在排序数组中查找元素的第一个和最后一个元素
代码
class Solution {
public:
int binary_search(vector<int>& nums, int target)
{
int left=0,right=size(nums)-1;
while(left<=right)
{
int mid = (left+right)/2;
if(target<=nums[mid]) right=mid-1;
else left=mid+1;
}
return right+1;
}
vector<int> searchRange(vector<int>& nums, int target) {
int left_idx = binary_search(nums,target);
int right_idx = binary_search(nums,target+1)-1;
if(right_idx>=left_idx)
{
return vector<int>{left_idx,right_idx};
}
return vector<int>{-1,-1};
}
};
总结
- 注意输出数组的写法
- 此处二分函数是找出不小于target的第一个元素——二分法找出的都是第一个等于target的元素的位置。
- 两次二分:第一次找出不小于target的第一个元素位置;第二次找出不小于target+1的第一个元素位置
- 值得多看!
rating:: ⭐⭐⭐⭐⭐
69. x的平方根
代码
class Solution {
public:
int mySqrt(int x) {
long long left=0,right = x;
while(left<=right)
{
long long mid = (left+right)/2;
if(mid*mid<=x) left = mid+1;
else right = mid-1;
}
return right;
}
};
总结
- 总觉得官方解法的第一种“袖珍计算器❓”法有点毛病😥,面试官应该更倾向于见到二分查找的方法,参照方法二吧
- 和上一题差不多,要想到用二分法,灵活变换二分法的判决条件
rating:: ⭐⭐⭐⭐⭐
367. 有效的完全平方数
代码
class Solution {
public:
bool isPerfectSquare(int num) {
long left=0,right = num;
while(left<=right)
{
long mid = (left+right)/2;
if(mid*mid<num) left = mid+1;
else if (mid*mid>num) right = mid-1;
else return true;
}
return false;
}
};
总结
- 上一题的简化版本