經(jīng)典的快速排序和二分查找
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

int Partition(int a[],int p,int r)
{
    int ran=rand()%(r-p+1)+p;       //隨即選取衛(wèi)兵
    swap(a[ran],a[r]);
    int x=a[r];
    int i=p-1;
    for (int j=p;j<r;j++)
    {
        if (a[j]<=x)               //小于衛(wèi)兵的值進(jìn)行對(duì)換
        {
            i++;
            swap(a[i],a[j]);
        }
    }
    swap(a[i+1],a[r]);
    return i+1;
}   

void QuickSort(int a[],int p,int r)
{
    int q;
    if (p<r)
    {
        q=Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}

int BinarySearch(int a[],int min,int max,int x)
{
    int mid;
    while (min<max)
    {
        mid=min+(max-min)/2;
        if (a[mid]>=x)
            max=mid;
        else
            min=mid+1;     //若不加一可能存在無限循環(huán)的結(jié)果
    }
    if (a[min]==x)
        return min;
    else if(a[max]==x)
        return max;
    else
        return -1;
}
void main()
{
    int num;
    cin>>num;
    int* a = new int[num];
    cout<<"排序前："<<endl;
    for(int i=0;i<num;i++)
        cin>>a[i];
    QuickSort(a,0,num-1);
    cout<<"排序后："<<endl;
    for (int j=0;j<num;j++)
    {
        cout<<a[j]<<endl;
    }
    cout<<"輸入要查找的數(shù)"<<endl;
    int x;
    cin>>x;
    int result=BinarySearch(a,0,num-1,x);
    if (result>=0)
        cout<<"目標(biāo)位置為:"<<result+1<<endl;
    else
        cout<<"目標(biāo)不在數(shù)組中"<<endl;
}