王争算法训练营5期 笔记

递归与分治

算法介绍

算法是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

二分搜索：

//从小到大排好序的数组list[low:high]中查找x
int binarySearch(int *list,int low,int high,int x)
{
    int left=low;
    int right=high;
    while(left<=right)
    {
        int minddle(left+right)/2;
        if(list[middle]==x)return middle;
        if(list[middle]<x)
            left=middle+1;
        else
            right=middle-1;
    }
    return -1;
}

 

归并排序：

//将a[low,mid]和a[mid+1，high]归并
void merge(int* a,int low,int mid,int high)
{
    int i=low;
    int j=mid+1;
    for(int k=low;k<=high;k++)
    {
        aux[k]=a[k];
    }
    for(int k=low;k<=high;k++)
    {
        if(i>mid)
            a[k]=aux[j++];
        else if(j>high)
            a[k]=aux[i++];
        else if(aux[i]<aux[j])
            a[k]=aux[i++];
        else
            a[k]=aux[j++];
    }
}

void mergeSort(int *list,int low,int high)
{
    if(high<=low)return ;
    int mid=(low+high)/2;
    mergeSort(list,low,mid);
    mergeSort(list,mid+1,high);
    merge(list,low,mid,high);
}