【普及】二分

· · 个人记录

二分

适用于一类具有单调性的问题。

二分查找

例题1：递增序列二分查找
洛谷 T164755 整数查找
模型：根据大小关系可将序列分为三个部分：a_i<x,a_i=x,a_i>x，这三个部分可以看作为-1,0,1的三段。
例题2：非减序列二分查找 洛谷 T164761 整数插入 模型：在非减序列中查找\ge x的数的第一次出现位置，可以将序列看作为0,1的两段，相当于查找分界线。