1.二分查找的原则

• 当要查找的值target>mid 就在mid和right中查找
• 当要查找的值target<mid就在left和mid中查找

对于边界条件的处理：

while(l<r)

mid的取值是[l,r)

重点是下面部分，直接决定使用哪个二分模板。

1.3 中间值归属问题
这个问题其实比较灵活，这里我只讨论3种情况，其余情况类似。假设有序数组为int[] nums，求解的是索引，根据题目要求分为3种情况：

情况一
假设我们要搜索的是大于6的最小值索引，如果num[mid] <= 6，那么这个mid一定不是目标索引，此时left = mid + 1（因为mid位置的值比目标值还小，而我们找的元素肯定大于目标值），如果如果num[mid] > 6，此时的mid是有可能是目标索引的，所以令right = mid；
情况二
假设我们要搜索的是小于6的最大值索引，如果num[mid] >= 6，那么这个mid一定不是目标索引，此时right = mid - 1（因为mid位置的值比目标值还大，而我们找的元素肯定小于目标值），如果如果num[mid] < 6，此时的mid是有可能是目标索引的，所以令left = mid；
情况三（最简单）
假设我们要搜索的是等于6的索引，如果num[mid] > 6，那么这个mid一定不是目标索引，此时right = mid - 1；如果如果num[mid] < 6，此时的mid也肯定不是目标索引，所以令left = mid + 1；如果num[mid] == 6，那就找到啦；

情况一：

while(l<r){
    int mid = l+r >>1;
    if(check(mid)) r= mid; //往小收缩
    else l= mid+1;
}
cout<<l;

情况二、三：

while(l<r){
    int mid = l+r+1 >>1;
    if(check(mid)) l = mid;//往大扩张
    else r= mid-1;
}
cout<<l;

2.DAG图的拓扑排序

DAG图：有向无环图

简单的拓扑排序就是：找到任意一个入度为0的点，将它删除，和它相连的边也删除。这样反复做，如果最后的图能删光，不留点和边，则可以生成一个拓扑序列，否则不能生成。

具体实现是用queue存储入度为0的点，当处理一个queue中的点时，将它链接的点的入度分别-1，如果有相连的点的入度变成0了，就将这个点放入queue。最后queue为空时进行最终的判断。

扩展：DAG中找路径条数，长度不限制 场景：食物链计数

方法：伪dp

//拓扑排序板子
//邻接表方法：
int n,m;
int h[5000005],ru[5000005],chu[5000005],f[5000005];
int tot;
int ans;

struct node{
    int v,nxt;
}d[5000005];

queue<int>q;

void add(int u,int v){
    d[++tot].v = v;
    d[tot].nxt = h[u];
    h[u] = tot;
}

void tpsort(){
    for(int i=1;i<=n;i++){
        if(ru[i]==0){
            q.push(i);
            f[i]++;//入度为0即为最弱的一个点，所以f[i]=1;
        }
    }
    while(!q.empty()){
        int p = q.front();
        q.pop();
        for(int i=h[p];i;i=d[i].nxt){
            int to = d[i].v;
            f[to] = (f[to]+f[p])%mod;
            ru[to]--;
            if(ru[to]==0){
                q.push(to);//将入度为0的点作为起始点。
            }
        }
    }
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        ru[b]++;
        chu[a]++;
    }
    tpsort();

    for(int i=1;i<=n;i++){
        // debug(ans);
        if(chu[i]==0) ans = (ans+f[i])%mod;
    }
    cout<<ans<<endl;   
}

3.链式向前星

设置三个数组:

head[u] 表示以u作为起点的第一条边的编号

nxt[cnt] 表示以cnt为边的下一条边。这条边和cnt同起点。

to[cnt] 表示编号为cnt的边的终点。

初始时令head[u] = cnt =0;表示尚未有边，每个点都是孤立点。

当加入一条新边e[u,v]时，

1. cnt++
2. nxt[cnt] = head[u] ;将原来以u作为起点的第一条边，作为该边的后续边。
3. to[cnt] = v; 当前边的终点位置

//不带权
void add(int u,int v)
{
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}

//带权
void add(int u,int v,int w)
{
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
    val[cnt]=w;
}

//遍历
for(int i=head[u];!i;i=nxt[i])   //广度遍历
{
    int v=to[i];
    //其他操作
}

//删边   删去一条边【u,vv】
int last=0;
for(int i=head[u];!i;i=nxt[i])
{
    int v=to[i];
    if(v==vv)
    {
        if(i==head[u]) head[u]=nxt[i];
        else nxt[last]=nxt[i];
        break;
    }
    last=i;
}