有序数列查找特定大小数的算法:二分查找(Binary Search)

凸函数或者凹函数寻找极值的算法:三分查找(Ternary Search)

二分查找

时间复杂度:$O(\log n)$

代码实现:

  • 整数:

查找 $\ge x$ 的第一个数:

(将 if (a[mid] >= x) 改为 if (a[mid] > x) ,可查找 $> x$ 的第一个数)

// a[ ]为储存数据的有序递增数组
// l ~ r为二分查找的数组范围
int l = 0, r = n - 1;
while (l < r)
{
    int mid = (l + r) / 2;
    if (a[mid] >= x)
    {
        r = mid;
    }
        else
    {
        l = mid + 1;
    }
}

查找 $\le x$ 的最后一个数:

(将 if (a[mid] <= x) 改为 if (a[mid] < x) ,查找 $< x$ 的最后一个数)

// a[ ]为储存数据的有序递增数组
// l ~ r为二分查找的数组范围
int l = 0, r = n - 1;
while (l < r)
{
    int mid = (l + r + 1) / 2;
    if (a[mid] <= x)
    {
        l = mid;
    }
        else
    {
        r = mid - 1;
    }
}
  • 实数:

查找满足一定条件的数:(即以下代码令 check(x) == true 的 x)

// check(int x): 判断x是否满足条件
// eps: 精度(因为浮点数误差,不可直接比大小)
// BEGIN: 查找左边界
// END: 查找右边界
bool check(int x);
double eps = 1e-6;
double l = BEGIN, r = END;
while (r - l > eps)
{
    double mid = (l + r) / 2;
    if (check(mid))
    {
        l = mid;
    }
    else
    {
        r = mid;
    }
}

STL 实现:

<algorithm>
lower_bound(begin, end, num)
upper_bound(begin, end, num)

  • 在有序递增数组中,查找 $\ge x(或> x)$ 的第一个数

lower_bound(begin, end, num): 从数组的 begin 位置到 end - 1 位置二分查找第一个大于或等于 num 的数字,找到返回该数字的地址,不存在则返回 end。

upper_bound(begin, end, num): 从数组的 begin 位置到 end - 1 位置二分查找第一个大于 num 的数字,找到返回该数字的地址,不存在则返回 end。

  • 在有序递减数组中,查找 $\le x(或< x)$ 的第一个数

lower_bound(begin, end, num, greater<type>() ): 从数组的 begin 位置到 end - 1 位置二分查找第一个小于或等于 num 的数字,找到返回该数字的地址,不存在则返回 end。

upper_bound(begin, end, num, greater<type>() ): 从数组的 begin 位置到 end - 1 位置二分查找第一个小于 num 的数字,找到返回该数字的地址,不存在则返回 end。

将返回的地址减去起始地址,得到数字在数组中的下标,如:

int position = lower_bound(num, num + 100, 64) - num;

这样,num[position] 就是找到的第一个大于等于 64 的数字。

算法思路:

以递增数组为例,将其分为两半。若中间值大于要找的数,说明要找的数在左边一半;若中间值小于要找的数,说明要找的数在右边一半。不断将范围缩小一半,直到找到要找的数。

三分查找

时间复杂度:$O(\log n)$

代码实现:

// f(double x): 给定区间内的凹函数或凸函数
// eps: 精度(因为浮点数误差,不可直接比大小)
// BEGIN: 查找左边界
// END: 查找右边界
double f(double x);
double eps = 1e-6;
double l = BEGIN, r = END;
while(r - l > eps)
{
    double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    if(f(m1) > f(m2))
    {
        l = m1;
    }
    else
    {
        r = m2;
    }
}

算法思路:

将 l ~ r 区间分为三份。如果 $f(m_1)<f(m_2)$,则极值点一定在区间 $(l,m_2)$;如果 $f(m_1)>f(m_2)$,则极值点一定在区间 $(m_1,r)$.

(只适用于区间内为单峰的函数)

标签: 二分查找, 三分查找

添加新评论