顺序查找
过于简单,不做介绍。
二分法(单调性)
二分查找:
从小到大
查找大于等于\(k\)最靠左的元素。
while(left<right)
{
mid=(left+right)>>1;
if(x[mid]<k)left=mid+1;
else right=mid;
}
查找小于等于\(k\)最靠右的元素。
while(left<right)
{
mid=(left+right+1)>>1;
if(x[mid]>k)right=mid-1;
else left=mid;
}
从大到小
查找大于等于\(k\)最靠右的元素。
while(left<right)
{
mid=(left+right+1)>>1;
if(x[mid]<k)right=mid-1;
else left=mid;
}
查找小于等于\(k\)最靠左的元素。
while(left<right)
{
mid=(left+right)>>1;
if(x[mid]>k)left=mid+1;
else right=mid;
}
二分答案:
最小值最大
while(left<right)
{
mid=(left+right+1)>>1;
if(check(mid))left=mid;
else right=mid-1;
}
最大值最小
while(left<right)
{
mid=(left+right)>>1;
if(check(mid))right=mid;
else left=mid+1;
}
细节的原理:抛弃肯定没有用的,留下可能有用的,为防止向下取整死循环,有一些情况需要加一。
注意事项:数学归纳法可证最终\(left=right\),即输出任意一个。
因为有等于,所以我上面似乎是相反的东西是不能通过\(+1\)或\(-1\)来互换的。
三分法
留坑待补。