算法第二章作业

huangroumin 2018-10-19 原文

算法第二章作业

1、对二分法思想的体会

首先，二分法体现的是分治的思想，通过不断一分为二的策略“逼近”结果；

其次，就算法应用而言，二分法主要应用在查找上，二分查找适用于数据量较大的有序数组，主要思想如下：设要查找的数组为array[0,n-1],要查找的元素为x,确定中间位置mid，首先将x与array[mid]比较，如果x==a[mid]，返回数租array的下标mid；如果x<a[mid]，则将数组缩小一半为array[0,mid-1]；如果x>a[mid]，则将数组缩小一半为array[mid+1,n-1]。如此递归查找即可；

最后，该算法的时间复杂度O(logN)。

代码实现：

#include<iostream>
using namespace std;
int binSearch(int a[],int x,int n){
    int left=0,right=n-1;
    int count=0;//比较次数
    while(left<=right){
        int mid=(left+right)/2;
        count++;
        if(x==a[mid])//查找的值正好在中间位置
        {
            cout<<mid<<endl;//输出下标
            cout<<count;
            return mid;
        }
        else if(x<a[mid])right=mid-1;
        else left=mid+1;

    }
    cout<<-1<<endl;
    cout<<count;

    
}
int main(){
    int n,x;
    cin>>n;
    int *a=new int(n);
    for(int i=0;i<n;i++)
    cin>>a[i];
    cin>>x;
    binSearch(a,x,n);
    return 0;
}

2、结队编程情况汇报

第一次以结队编程的形式去打代码，和队友一起合作去解决问题还是很有成就感的，和自己闷头去打代码的感觉很不一样的。比如这个二分查找的算法，虽然课本已经有现成的代码，但我们还是选择自己一步一步自己去把代码敲出来，在这个过程中还是会遇到许多问题的。比如这行代码一开始就放错了位置：int mid=(left+right)/2;如果靠我自己闷头去想，恐怕就很难发现错误，这就是所谓的“当局者迷”，而如果旁边有人提醒，就会很高效地解决问题。另外，在这个过程中，她还提醒了我，循环是需要返回值的，不然就会陷入死循环。所以，希望今后可以继续合作下去，共同进步！

posted on 2018-10-19 09:34 huangroumin 阅读(…) 评论(…) 编辑收藏