# 演算法導論 HW3
https://hackmd.io/@wang1234/rkPRftnxq
## 第1題: Insertion Sort
<font color="DimGray" class="small">* 請依據課本推導方式，當5個數字用insertion sort排序，data movement的平均值為多少？</font>
*average case:*
n=5 , X=(5+8)(5-1)/4=<font color="DeepSkyBlue">13</font>

<font color="DimGray" class="small">* 請使用insertion sort排序 6,4,1,3,5。在四個回合中，每回合的data movement數量為何？總共的data movement數量為何？</font>

| j | 排序情況 | data movement數量 |
| -------- | -------- | -------- |
| | 6,4,1,3,5 | |
| | <font color="LimeGreen">6</font>,4,1,3,5 | |
| 2 | <font color="LimeGreen">4,6</font>,1,3,5 | 2+1=<font color="DeepSkyBlue">3</font> |
| 3 | <font color="LimeGreen">1,4,6</font>,3,5 | 2+2=<font color="DeepSkyBlue">4</font> |
| 4 | <font color="LimeGreen">1,3,4,6</font>,5 | 2+2=<font color="DeepSkyBlue">4</font> |
| 5 | <font color="LimeGreen">1,3,4,5,6</font> | 2+1=<font color="DeepSkyBlue">3</font> |
| | | (加總)<font color="DeepSkyBlue">13</font> |

## 第2題: Binary Search
<font color="DimGray" class="small">* 算出15個有序數列使用Binary Search，平均的比對次數為何？</font>
*average case:*
n=15 , k=4 ,
A(n)=(1/(2×15+1))×(2⁴×(4-1)+1+4×(15+1))
=(1/31)*(49+64)=3.64...≒<font color="DeepSkyBlue">4</font>

## 第3題：完全平方數
[367. Valid Perfect Square](https://leetcode.com/problems/valid-perfect-square/)
<font color="Black">
解題思路:
> num平方根一定大於等於0,小於等於⌊num/2⌋+1,
> 在二元搜尋的迴圈中,如果num小於mid的平方,調整右邊界至mid-1;
> 反之,如果num大於mid的平方,調整左邊界至mid+1,
> 而如果num剛好等於mid的平方,表示num為完全平方數,返還True,
> 若是直到while迴圈結束,都沒找到整數的num的平方根,就返還False
</font>

class Solution(object):
    def isPerfectSquare(self, num):
        left,right=0,int(num/2)+1
        while left<=right:
            mid=(left+right)//2
            if num<mid**2:
                right=mid-1
            elif num>mid**2:
                left=mid+1
            else:     # mid**2==num
                return True
        return False

花15分鐘，完全靠自己

## 第4題：尋找字元
[744. Find Smallest Letter Greater Than Target](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)
解題思路:

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        if target>=letters[-1]:
            return letters[0]
        left,right=0,len(letters)-1
        while left<right:
            mid=(left+right)//2
            if target<letters[mid]:
                right=mid
            else:
                left=mid+1
        return letters[right]

花25分鐘，完全靠自己

## 第5題：尋找山頂
[852. Peak Index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/)
<font color="Black">
解題思路:
> 以arr=[0,<font color="LimeGreen">1</font>,0]和arr=[2,4,5,7,<font color="LimeGreen">8</font>,5,3,1]為例,
> 不難發現在山頂的左側的每個數,都比其右邊(mid+1)的數小;
> 而山頂的的右側的數,都比其左邊(mid-1)的數小,
> 最後,當抓到的數比它左右兩邊的數都要大時,此處即為山頂
</font>

class Solution(object):
    def peakIndexInMountainArray(self, arr):
        left,right=0,len(arr)-1
        while left<=right:
            mid=(left+right)//2
            if arr[mid]<arr[mid+1]:
                left=mid+1
            elif arr[mid]<arr[mid-1]:
                right=mid-1
            else:
                return mid

花30分鐘，完全靠自己

## 第6題：在平移後的數列中，尋找最小值
[153. Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
解題思路:

class Solution(object):
    def findMin(self,nums):
        if nums[0]<nums[-1] or len(nums)<2:
            return nums[0]
        elif nums[-1]<nums[-2]:
            return nums[-1]
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]>nums[mid-1]:
                if nums[mid]<nums[0]:
                    right=mid-1
                else:    #nums[mid]>=nums[0]
                    left=mid+1
            else:
                return nums[mid]

花70分鐘，完全靠自己

## 心得
這次作業中花費較多時間的部分,除了前兩題觀念題以外,就是第6題,由於一開始對題目測資情況的分析不夠,所以修改好幾次