博客

二分搜索（lower_bound详解)

  • Post author:
  • Post category:其他


  1. lower_bound是一种应用于有序数据范围内的算法，它可以返回一个迭代器，这个迭代器指向第一个不小于指定值value的元素。
  2. 用途：可以找出第一个能恰当插入value的位置，且能维持指定范围内的元素顺序（有序状态）。
  3. 用法：lower_bound（）的前两个参数用来指定作为对象的数组或容器的范围。第三个参数用来指定value。
  4. 例题：ALDS1_4_B

    #include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int n, s[100005];
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> s[i];
    }

    int q, k;
    int sum = 0;
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        cin >> k;
        if(*lower_bound(s, s+n, k) == k)
            sum++;
    }

    cout << sum << endl;

    return 0;
}


版权声明：本文为Jefferson__原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。