一、折半查找

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N];
int n,key;
int binary_search()
{
    int low=0,high=n-1;
    while(low<=high)
    {
        int mid=low+high>>1;
        if(q[mid]==key)
            return mid;
        else if(q[mid]>key)
            high=mid-1;
        else 
            low=mid+1;
    }
    return -1;
}
int main()
{
    cin>>n>>key;
    for(int i=0;i<n;i++)
        cin>>q[i];
    int index=binary_search();
    if(index==-1)cout<<"查找失败";
    else 
        cout<<index;
    return 0;
}

二、查找链表节点

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int val;
    Node* next;
    Node(int x):val(x),next(NULL){}
};
Node* createListNode2(int val[],int n)
{
    if(n==0)
        return NULL;
    Node* dummy=new Node(-1);
    Node* cur=dummy;
    for(int i=0;i<n;i++)
    {
        Node* p=new Node(val[i]);
        cur->next=p;
        cur=cur->next;
    }
    return dummy->next;
}
int kthToLast(Node* head,int k)
{
    int n=0;
    for(auto p=head;p;p=p->next)
        n++;
    auto p=head;
    for(int i=0;i<n-k;i++)
        p=p->next;
    return p->val;
}
int main()
{
    int a[] = {6, 9, 5, 12, 3};
    int n = sizeof(a) / sizeof(a[0]);
    Node *head = createListNode2(a, n);
    cout << kthToLast(head, 3) << endl;
    return 0;
}

三、共享栈

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
struct SharedStack
{
    int e[N];
    int top0;
    int top1;
    SharedStack():top0(-1),top1(N){}
};
void push0(SharedStack* s,int x)
{
    if(s->top0+1==s->top1)
        cout<<"栈溢出"<<endl;
    else
        s->e[++s->top0]=x;
}
void push1(SharedStack* s,int x)
{
    if(s->top0+1==s->top1)
        cout<<"栈溢出"<<endl;
    else
        s->e[--s->top1]=x;
}
int pop0(SharedStack* s)
{
    if(s->top0<0)
    {
        cout<<"栈0已空,出栈失败"<<endl;
        return -1;
    }
    else
        return s->e[s->top0--];
}
int pop1(SharedStack* s)
{
    if(s->top1>=N)
    {
        cout<<"栈1已空,出栈失败"<<endl;
        return -1;
    }
    else
        return s->e[s->top1++];
}
int main() 
{
    SharedStack* s = new SharedStack();
    push0(s, 1);
    push0(s, 2);
    push1(s, 11);
    push1(s, 12);
    cout << "Pop from s0: " << pop0(s) << endl;
    cout << "Pop from s1: " << pop1(s) << endl;
    cout << "Pop from s0: " << pop0(s) << endl;
    cout << "Pop from s1: " << pop1(s) << endl;
    return 0;
}

四、最大不相交区间数量

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct Range
{
    int l;
    int r;
    bool operator < (const Range& t)const
    {
        return r<t.r;
    }
}range[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    sort(range,range+n);
    int ans=0,ed=-2e9;
    for(int i=0;i<n;i++)
    {
        if(range[i].l>ed)
        {
            ans++;
            ed=range[i].r;
        }
    }
    cout<<ans;
    return 0;
}