普通二分搜索
while(l while(l while(l<=r) l=0,r=n-1 l==r+1 [l,r] 1.寻找第一个满足条件的元素 2.寻找最后一个满足条件的元素 y总的记忆法 欢迎分享,转载请注明来源:内存溢出
int binary_search(int x)
{//普通二叉搜索,查找某个元素,返回下标
int l = 0;
int r = n; //数组长度
//l
如果一个x有多个,二分搜索分为两种情况:
int left_bound(int x)
{//寻找x的第一个出现的下标
//也可以理解为:数组中有几个小于x的数字,可能的返回值取值为[0,n]
int l = 0, r = n;
//l
2.寻找最后一个满足条件的值
int right_bound(int x)
{
int l = 0, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] < x) //x在右边
l = mid + 1; //去区间[mid+1,r)寻找
else if (a[mid] > x) //x在左边
r = mid; //去区间[l,mid)寻找
else if (a[mid] == x) //找到了x不是立即返回,而是去右边继续寻找
l = mid + 1;
}
if (l == 0)return -1;
return a[l - 1] == x ? l - 1 : -1;
l = 0, r = n - 1;
//while(l<=r) 循环终止l==r+1,循环区间[l,r)
while (l <= r)
{
int mid = l + r >> 1;
if (a[mid] < x) //x在右边
l = mid + 1; //去区间[mid+1,r]寻找
else if (a[mid] > x)
r = mid - 1; //去区间[l,mid-1]寻找
else if (a[mid] == x) //继续寻找右侧端点
l = mid + 1; //去区间[mid+1,r]寻找
}
//循环终止条件为l==r+1,所以只要r不越界,那么r的值就是x的右侧边界,不需要l-1
if (r < 0 || a[l] != x)
return -1;
return r;
}
int acwing(int x)
{
//搜索左侧边界
//[l,r]分为[l,mid],[mid+1,r]
//[l,mid]保证了不漏
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
if (a[mid]>=x) //x在左边,去左边寻找左侧边界
r = mid;
else l = mid + 1;
}
return l;
//搜索右侧边界
//[l,r]分为[l,mid-1][mid,r]
//[mid,r]保证了不漏
l = 0, r = n - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1; //写了l=mid,mid就+1
if (a[mid] <= x) l = mid;
else r = mid - 1;
}
return l;
//p.s.mid = (l + r + 1) / 2这里,+1是因为除法下取整,
//在r = l + 1时更新l = mid时会出现l = mid = l的死循环。+1则相当于上取整,解决了这个隐患。
}
//写成l=mid mid=(l+r+1)/2
//写成l=mid+1 mid=(l+r)/2
评论列表(0条)