3.13日算法 上机作业

题目：以递归和分治的思想实现二分搜索

题目分析，二分搜索是在解空间有序的情况下，取整体中间的值与目标值进行对比，如果与目标值相同，那么就是所求解，否则，若比中间值大，则删去小的那一半，这样每次可以减少一半的查询，二分搜索的复杂度应该为 O(log n) ，对于整个程序来说，我们要让一个随机的数组有序，调用algorithmn 库的中函数sort ，此时的时间复杂度应该O (nlogn) ，因此在这种情况下，整个程序中时间开销最大的应该是排序的时间，所以整个程序的时间复杂度应该为 O(nlogn)

代码如下

#include <bits/stdc++.h>
#define cl(arr) memset(arr,0,sizeof(arr))
#define fl(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int maxn=1e5+50;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef pair<int,int>PII;
typedef long long ll;
int n;
int a[maxn];
int pos=-1;
void binarysearch(int x,int l,int r)
{
    if(l==r)
    {
        if(x==a[l]) pos=l;
        return;
    }
    int mid=l+(r-l)/2;
    if(a[mid]==x)

    {
        pos=mid;
        return;
    }
    if(a[mid]>x)
    {
        binarysearch(x,l,mid);
    }
    else
    {
        binarysearch(x,mid+1,r);
    }
}
int main()
{
    srand((unsigned)time(NULL));
    for(int i=1; i<=100; i++)
    {
        a[i]=rand()%500;
    }
    sort(a+1,a+101);
    for(int i=1; i<=100; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    int k;
    scanf("%d",&k);
    binarysearch(k,1,100);
    if(pos==-1)
    {
        puts("NOT EXIST");
    }
    else printf("%d\n",pos);
    return 0;
}

输出分析：本程序通过查找数组中的某一个数，返回该数在数组的中索引。通过二分的方式查找该索引。