对二分法思想的理解和结对编程的感想

一、对二分法的理解

1. 基本思想:假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功;若x小于当前位置值，则在数列的左半段中查找;若x大于当前位置值则在数列的右半段中继续查找，直到找到为止。
2. 优点：当数据量很大适宜采用该方法，可以提高效率。
3. 特点：有序排列，存储在数组中。
4. 缺点：如果存储在链表中，则不能采用二分法。
5. 时间复杂度：每执行一次算法的while循环，待搜索数组的大小减小一半，在最坏的情况下，while被执行了O(logn)次，最好的情况为x所对应的值在序列的中间位置，while被执行了O(1)次。所以二分法时间复杂度为O(logn)。
6. 实现方法：

   //1.循环
   int BinarySearch(int a[],int left,int right,int x){
       while (left<=right){
           int middle =(left+right)/2;
           if (x==a[middle]){
               return middle;
           }
           if(x>a[middle]){
               left=middle+1;
           }
           else {
               right =middle-1;
           } 
       }
       return -1;
   }

   //2.递归
   int binarysearch(int a[], int left, int right, int x)
   {
       if (left > right) return -1;
       int mid = (left + right)/2;
       if (a[mid]> x)
           return    binarysearch(a, left, mid -1, x);
       else if (a[mid]< x)
           return    binarysearch(a, mid+1, right, x);
       else if (a[mid]==x)
           return mid;
   }

 

二、结对编程的感悟

　　今天在算法课上两个人一起打代码，事实证明有个人看着我打代码真的可以减少很多傻乎乎的Bug，没有思路的时候还可以讨论各自的想法，会让本来很枯燥的打代码变得很有趣。此外，还可以多一点学习别人的代码，学习别人的优点，补充自己的不足之处。希望以后可以和我的拍档相互监督，相互学习，一起进步。