第二章作业心得
首先想讲一下二分法的理解：
在和我的小伙伴一起学习的条件下面，我们两个都是觉得二分法就是给出定值K，然后与表中的中间元素进行关键字比较，若相等，中，则向右查找，直到找到关键词的我们则返回他的存储位置；如果不等的话，则如二分查找算法题位置。
本次作业中二分法的运用体现在第一题的寻找第K小的数上，首先定义了partition函数来实现了根据a[left]~a[right]中的某个元素x（如a[left])对a[left]~a[right]进行划分，划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。
int partition(int a[],int left, int right){
int x = a [left];
while (left <right )
{
while (left < right && a[right] >= x)
right--;
a [left] = a [right];
while (left<right &&a [left] <= x)
left++;
a[right] = a[left];
}
a[left]=x;
return left;
}
然后也写出了find函数来实现查找功能
int find(int a[], int left, int right, int k)
{
int pos = partition(a,left,right);
if (k -1 ==pos)
cout<<a[k-1];
else if (k-1<pos)
find(a,left,pos -1,k);
else
find(a,pos+1,right,k);
return 0;
}
最后利用mian函数来实现此功能
int main()
{
int n, k;
cin >>n>>k;
int a[1000];
for(int i =0; i<n; i++)
cin >>a[i];
find(a,0,n-1,k);
return 0;
}
心得体会
二分法感觉就是一门比较方便的查找方法，而且使用起来也比较简单，理解起来也很快。重要的是对于我们这种学生还是要把编程能力打扎实了吧，所以以后还是会把课本以及课堂的作业都好好敲出来，争取不借助课本等实现算法。
原文：https://www.cnblogs.com/chickenbro666/p/9788796.html