對二分演算法的理解及結對程式設計情況
摘要：對二分演算法的理解及結對程式設計情況
1 二分演算法，又稱折半演算法，是應用分治策略的典型例子。時間複雜度為O(logn)，效率高。
2 基本思想：將n個元素（已排好序）分成個數大致相同的兩半，取a[n/2]與x作比較。如果a[n/2]=x，則找到x，演算法終止；如果x<a[n/2]，則只...
對二分演算法的理解及結對程式設計情況
1 二分演算法，又稱折半演算法，是應用分治策略的典型例子。時間複雜度為O(logn)，效率高。
2 基本思想：將n個元素（已排好序）分成個數大致相同的兩半，取a[n/2]與x作比較。如果a[n/2]=x，則找到x，演算法終止；如果x<a[n/2]，則只在陣列a的左半部繼續搜尋x；如果x>a[n/2]，則只在a的右半部繼續搜尋x。（每執行一次while迴圈，待搜尋的陣列大小減小一半，因此，在最壞情況下，while迴圈被執行了O(logn)次。迴圈體內運算需要O(1)次時間，因此，整個演算法的時間複雜度為O(logn)。
3 遞迴演算法程式碼：
4 非遞迴演算法程式碼：
5 結對程式設計情況：結對程式設計，遇到難題，可以相互討論，互相學習。也要求我們將程式碼寫的簡明易懂，同時學會看別人的程式碼。