# 演算法 HW3

## :book: 觀念題

### 第一題 Insertion Sort
* 請依據課本推導方式，當5個數字用insertion sort排序，data movement的平均值為多少？
$$
x=\sum\limits_{j = 2}^5{{j+3 \over 2}} ={(5+8)(5-1) \over 4}=13
$$
* 請使用insertion sort排序 6,4,1,3,5。在四個回合中，每回合的data movement數量為何？總共的data movement數量為何？

* **第一回合**:
6 4 1 3 5 ==4== --> 1+1+1=3 (搬動6)
* **第二回合**:
4 6 1 3 5 ==1== --> 1+2+1=4 (搬動4、6)
* **第三回合**:
1 4 6 3 5 ==3== --> 1+2+1=4 (搬動4、6)
* **第四回合**:
1 3 4 6 5 ==5== --> 1+1+1=3 (搬動6)
$$
8+\sum_{i = 2}^5{d_i}=8+(1+2+2+1)=14
$$
**共 3+4+4+3=14**

### 第二題 Binary Search
* 請參考投影片25頁與26頁，算出15個有序數列使用Binary Search，平均的比對次數為何？
* 解一
$$
A(n)=(1*1+2*2+3*4+4*8)/(15+16)=113/31\approx3.645
$$
* 解二
$$
A(n)=1/31(2^4(4-1)+1+4*(15+1))\approx3.645
$$
## :desktop_computer: 程式題 (使用語言 : C++)

### 第三題 二元搜尋應用：完全平方數

* leetcode 367
* 時間:10分鐘
* 自己完成的程度 : 完全靠自己
* 思路 :
:::success
取中間值判斷該數平方後是否為num。
若是，則該數即為答案。
若該數平方後==小於==num，別表示其解比該數大，故向右尋找。
若該數平方後==大於==num，別表示其解比該數小，故向左尋找。
:::
* 程式碼 :

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left=1;
        int right=num;
        int mid;
        bool ans=false;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            
            if(num/mid==mid && num%mid==0)
            {
                ans=true;
                break;
            }
            else if(num/mid<mid)
                right=mid-1;
            else
                left=mid+1;
        }
        return ans;
    }
};

* 通過截圖


### 第四題 尋找字元

* leetcode 744
* 時間:10分鐘
* 自己完成的程度：完全靠自己
* 思路 :
:::success
該字元序列以遞增排序，且要找到比target字元大的最小字元，使用二元搜尋法取中間值判斷
* 若該字元==等於或小於==target，則向右尋找。
* 若該字元==大於==target，則判斷次字元是否有比上一次找到比target字元大的字元小
* 若此字元==等於或小於==上一次找到比target字元大的字元，則將此字元存起來用於下一次的判斷。
* 若此字元==大於==上一次找到比target字元大的字元，則將其略過。
完成以上判斷後，繼續向此字元的左邊尋找是否有更小且比target字元大的字元。
* 因字元順序是循環的，且字元序列以遞增排序，若沒找到比target字元大的最小字元，則回傳該序列的最小字元。
:::
* 程式碼:

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left=0;
        int right=letters.size()-1;
        int mid;
        char ans='z';
        bool found=false;
        while(left<=right)
        {
            mid=left+(right-left)/2;
            if(letters[mid]<=target)
            {
                left=mid+1;
            }

            else
            {
                if(letters[mid]<=ans)
                {
                    ans=letters[mid];
                    found=true;
                }

                right=mid-1;
            }
        }
        if(found)
            return ans;
        else
            return letters[0];
    }
};

* 通過截圖

### 第五題 尋找山頂

* leetcode 852
* 時間:50分鐘
* 自己完成的程度：完全靠自己
* 思路 :
:::success
本題要找的是最大值，且順序為由小到大再到小，因此，
若找到一個數的前一個與後一個數都比此數小，那此數即為所求。
若前一個數小於此數，且後一個數大於此數，則向此數的==右邊==尋找。
若前一個數大於此數，且後一個數小於此數，則向此數的==左邊==尋找。
:::
* 程式碼:

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left=0;
        int right=arr.size()-1;
        int mid;
        int ans;
        while(left<right)
        {
            mid=left+(right-left)/2;

            if(mid==0 && arr[mid+1]>arr[mid])
                return 1;
            else if(mid==arr.size()-1 && arr[mid]>arr[mid-1])
                return mid;
            if(arr[mid-1]<arr[mid] && arr[mid+1]<arr[mid])
            {
                return mid;;
            }
            else if(arr[mid-1]<arr[mid] && arr[mid+1]>arr[mid])
            {
                left=mid+1;
            }
            else if(arr[mid-1]>arr[mid] && arr[mid+1]<arr[mid])
            {
                right=mid-1;
            }

        }
        return left;
    }
};

* 通過截圖


## :pushpin:心得

### 第六題 本週心得

這次作業相對簡單很多，寫起來也比較有成就感，雖然簡單，卻可以從中更熟悉二元搜尋的應用。
也發現，這些題目題型都很相似，解題時的思路其實都差不多。
但老實說，影片其實有點聽不太懂，觀念題寫的都有點艱辛。

###### tags: `演算法`