手写二分
int l=0,r=n-1; while(l<=r){ int mid=l+(r-l)/2; if(a[mid]==x) ...; else if(a[mid]<x) l=mid+1; else r=mid-1; }
STL 二分
lower_bound(a.begin(),a.end(),x) 返回第一个 ≥x 的迭代器,减 begin() 得下标;upper_bound 返回第一个 >x 的位置。
加载中…
C++ 机试动画
本课导读
二分查找把有序数据里的查找压到 O(log n),是机试高频。这一课讲手写二分模板和 STL 的 lower_bound / upper_bound。
int l=0,r=n-1; while(l<=r){ int mid=l+(r-l)/2; if(a[mid]==x) ...; else if(a[mid]<x) l=mid+1; else r=mid-1; }
lower_bound(a.begin(),a.end(),x) 返回第一个 ≥x 的迭代器,减 begin() 得下标;upper_bound 返回第一个 >x 的位置。
把 C++ 做题手感练出来
这套课只讲机试最常用的 C++：输入输出、类型、数组、字符串和 STL。先把这些模板练熟，再去刷数据结构和算法题，效率会高很多。