递归与分治
算法介绍
算法是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
二分搜索：
//从小到大排好序的数组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;
}
//从小到大排好序的数组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);
}
//将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);
}