• 顺序查找

过于简单,不做介绍。

  • 二分法(单调性)

二分查找:

从小到大

查找大于等于\(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\)来互换的。

  • 三分法

留坑待补。

02-10 06:00