1.折半查找

#include <iostream>
using namespace std;
const int N=10010;
int a[N];

int BinarySearch(int a[],int n,int x)
{
    int low=0,high=n-1;
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(a[mid]==x) return mid;
        else if(a[mid]<x)low=mid+1;
        else high=mid-1;
    }
    return -1;//查找失败
}

int main()
{
    int n,x;
    cin>>n>>x;
    for(int i=0;i<n;i++)
    cin>>a[i];

    int index=BinarySearch(a,n,x);
    if(index==-1)cout<<"查找失败"<<endl;
    else cout<<"查找成功,待查元素下标为："<<index<<endl;
    return 0;
}
/*
5 13
3 5 6 8 13 
*/

2.查找链表节点

#include <iostream>
using namespace std;

const int N=100010;
int a[N];
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};
int kthToLast(ListNode* head,int len,int k)
{
    int cnt=0;

    for(ListNode*p=head;p;p=p->next)
    {
        cnt++;
        if(cnt==(len-k+1))
            return p->val;
    }
    return -1;
}

ListNode* creadeListNode(int vals[],int n)
{
    ListNode*dummy=new ListNode(-1);
    ListNode*tail=dummy;
    for(int i=0;i<n;i++)
    {
        ListNode*t=new ListNode(vals[i]);
        tail->next=t;
        tail=t;
    }
    return dummy->next;
}

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    cin>>a[i];

    ListNode*head=creadeListNode(a,n);
    int len=0;
    for(ListNode *p=head;p;p=p->next)
    {
        len++;
    }
    int res=kthToLast(head,len,k);
    cout<<res;
    return 0;
}

/*5 2
6 9 5 13 3*/

3.共享栈

#include <iostream>
using namespace std;
const int maxsize=100;

struct ShareStack
{
    int e[maxsize];
    int top0;
    int top1;
    ShareStack():top0(-1),top1(maxsize){}
};

void push0(ShareStack &s,int x)
{
    if(s.top0+1>=s.top1)
        cout<<"栈0发生上溢出"<<endl;
    else
        s.e[++s.top0]=x;
}
int pop0(ShareStack &s)
{
    if(s.top0==-1)
    {
        cout<<"栈0发生下溢出"<<endl;
        return -1;
    }
    else 
        return s.e[s.top0--];
}

void push1(ShareStack &s,int x)
{
    if(s.top1-1<=s.top0)
        cout<<"栈1发生上溢出"<<endl;
    else
        s.e[--s.top1]=x;
}
int pop1(ShareStack &s)
{
    if(s.top1==maxsize)
    {
        cout<<"栈1发生下溢出"<<endl;
        return -1;
    }
    else 
        return s.e[s.top1++];
}

int main()
{
    ShareStack s;
    push0(s,4);
    push0(s,92);
    push1(s,87);
    push1(s,5);

    cout<<pop0(s)<<endl;
    cout<<pop1(s)<<endl;
    cout<<pop0(s)<<endl;
    cout<<pop1(s)<<endl;

    return 0;
}