#include <iostream>

using namespace std;

//快排

void quickSort(double *q ,int n)   //一个double型数组还有一个代表这个数组的位数。

{

    double *left,*right;

    left = &q[0];

    right = &q[n-1];

    double middle = q[0];

//    cout<<"left指向数组第一位，值为"<<*left<<endl;

//    cout<<"right指向数组最右一位，值为"<<*right<<endl;

    while(left != right)

    {

        if (*right < middle)

        {

            *left = *right;

            while (*left < middle)

            {

                left++;

                if (left == right)

                {

                    break;

                }

            }

            *right = *left;

        } else {

            right--;

        }

    }

    //左右指针指向一致时把middle给这个位置

    *left = middle;

    //接下来取得*left和*right指向数组的位数

    int count = 0;   //count1表示有count1个数在middle左边，最小为0

    for(;q[count]<middle;count++) { }

    //

    //处理middle的左边

    if (count>1)

    {

        double *qq = new double[count];

        qq = q;

        quickSort(qq,count);

    }

    //处理middle的右边

    int count2 = n-count-1; //count2表示有count2个数在middle右边，最小为0

    if (count2 > 1)

    {

        double *ww = new double[count2];

        ww = left+1;

        quickSort(ww,count2);

    }

}

//折半查找

void binarySearch(double *p ,int length,double g) {

    bool b = false;

    int left = 1,right = length;

    int middle = (left + right) / 2;

    if (g == p[middle-1])

    {

        cout<<"该数字是第"<<middle<<"位"<<endl;

    } else {

        while (g != p[middle-1])

        {

            if (left == right)

            {

                cout<<"该数字不在数组中"<<endl;

                b = true;

                break;

            }

            if (g>p[middle-1])   //因为数组从零开始所以减一

            {

                left = middle + 1;

            } else {

                right = middle - 1;

            }

            middle = (left + right) / 2;

        }

        if (b == false)

        {

            cout<<"该数字是第"<<middle<<"位"<<endl;

        }

    }

}

int main() {

    cout<<"请输入数组长度";

    int n;

    cin>>n;

    double *p = new double[n];

    for (int i = 0;i<n;i++)

    {

        cin>>p[i];

    }

    quickSort(p,n);

    for (int xxx = 0;xxx<n;xxx++)

    {

        cout<<p[xxx]<<"    ";

    }

    cout<<endl<<endl;

    //设(left+right)/2是中间位置

    double g;

    cout<<"输入要查的数字"<<endl;

    cin>>g;

    binarySearch(p,n,g);

    return 0;

}