我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分搜索 >

CC++利用 upper_bound和lower_bound的性质二分查找

归档日期:07-07       文本归类:二分搜索      文章编辑:爱尚语录

  第一行一个整数N,代表有N个数,这N个数不一定有序。N=100万。

  对于每一次询问,输出这个整数M所在的下标(在原数组中的下标,并不是你排好序以后的下标,这一点请注意),数据保证所有数不重复。如果找不到,输出-1.

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  两个函数的用法类似,在一个左闭右开的有序区间里进行二分查找,需要查找的值由第三个参数给出。

  对于upper_bound来说,返回的是被查序列中第一个大于查找值的指针,也就是返回指向被查值查找值的最小指针,lower_bound则是返回的是被查序列中第一个大于等于查找值的指针,也就是返回指向被查值=查找值的最小指针。

  不过除此之外,这两个函数还分别有一个重载函数,可以接受第四个参数。如果第四个参数传入greaterType(),其中Type改成对应类型,那么upper_bound则返回指向被查值查找值的最小指针,lower_bound则返回指向被查值=查找值的最小指针。

本文链接:http://pikeducation.com/erfensousuo/497.html