大理石在哪儿 sort+lower_bound

作者： 作者的头像   xianhai ,  2021-11-21 18:54:57 ,  所有人可见 ,  阅读 258

2


算法竞赛入门经典（第二版）大理石在哪儿 p108

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int n, q, x, a[maxn], k;

int main() {
    while (scanf("%d%d", &n, &q) == 2 && n) {
        printf("CASE# %d\n", ++k);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        while (q--) {
            scanf("%d", &x);
            int p = lower_bound(a, a + n, x) - a;
            if (a[p] == x) {
                printf("%d found at %d\n", x, p + 1);
            } else {
                printf("%d not found\n", x);
            }
        }
    }
    return 0;
}

测试数据

4 1
2 3 5 1
5
5 2
1 3 3 3 1
2 3

http://www.cplusplus.com/reference/algorithm/lower_bound/
https://www.jianshu.com/p/cb0d5488bb6a

3 评论

用户头像
xianhai   2021-11-22 13:02         踩      回复 
template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}
用户头像
xianhai   2021-11-22 11:25         踩      回复

ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中第一个大于val的位置。

用户头像
xianhai   2021-11-22 11:07         踩      回复

#### Markdown基本语法
https://www.jianshu.com/p/191d1e21f7ed