演算法第二章作業
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;如果靠我自己悶頭去想,恐怕就很難發現錯誤,這就是所謂的“當局者迷”,而如果旁邊有人提醒,就會很高效地解決問題。另外,在這個過程中,她還提醒了我,迴圈是需要返回值的,不然就會陷入死迴圈。所以,希望今後可以繼續合作下去,共同進步!