# 演算法作業 HW2
## 1.
## 2.

## 3.數列被轉置
- 程式碼

   class Solution {
    public:
    int search(vector<int>& nums, int target) {
            
        int left=0;
        int right=nums.size()-1;
        while(left<=right)
        {
            
            int mid=int((left+right)/2);
            if(nums[mid]==target)
            {
                return mid;
            }
            if(nums[mid]<nums[right])//代表mid以後是有序的
            {
                if( nums[mid]<target&&nums[right]>=target)//目標在mid+1之後
                {
                    left=mid+1;
                }
                else
                {
                  right=mid-1;  
                  
                }
                 
            }
            else //mid以前是有序的
            {
                if (nums[left]<=target&&nums[mid]>target)//目標在mid-1
                {
                    right=mid-1;
                    
                }
                else
                {
                    left=mid+1;
                }
            }
        }
        return -1;    
        }
    };

- 圖片
![](https://i.imgur.com/JlvVGya.png)
- 花費時間:二小時半
- 自己完成程度：沒有頭緒，ｇｏｏｌｅ以後並理解程式碼跟觀念
- 解題思路
  - 關鍵:不知道這組數字在哪邊開始旋轉?
  - 舉例:  0　　1　　2　　 4　　5　　6　　7 有七種旋轉方法
  0　　1　　2　　 **4**　　**5**　　**6**　　**7**

    7　　0　　1　　 **2**　　**4**　　**5**　　**6**

    6　　7　　0　　 **1**　　**2**　　**4**　　**5**

    5　　6　　7　　 **0**　　**1**　　**2**　　**4**

    **4**　　**5**　　**6**　　 **7**　　0　　1　　2

    **2**　　**4**　　**5**　 　**6**　　7　　0　　1

    **1**　　**2**　　**4**　　 **5**　　6　　7　　0


  - 二元搜尋法是以mid為分割點，判斷要搜索前半段還是後半段，
加粗的地方都是升序，發現分為兩類
1.前半段是排序好的
2.後半段是排序好的
  -  判斷方法:找出規律，如果中間數大於最右邊的數，則為類１，反之，則為類２
關鍵：只要在排序好的那段，利用頭尾數值來判斷使否目標落在區間，就可以確定要保留哪半！

## ４.數字可能重複，回傳範圍
- 程式碼

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int ans[2];
ans[0]=searchleft(nums,target);
ans[1]=searchright(nums,target);
return{ans[0],ans[1]};
}
private:
int searchleft(vector<int>& nums, int target)
{
int left=0;
int right=nums.size()-1;
while(left<=right)
{
int mid=int(left+(right-left)/2);//防止溢位
if(nums[mid]==target)
{
if(mid==0||nums[mid-1]<target)//如果是邊界
{
return mid;

}
right=mid-1;//如果不是邊界縮小範圍
}
//二元搜尋法
if(nums[mid]<target)
{
left=mid+1;
}
if(nums[mid]>target)
{
right=mid-1;
}
}
return -1;
}
int searchright(vector<int>& nums, int target)
{
int left=0;
int right=nums.size()-1;
while(left<=right)
{
int mid=int(left+(right-left)/2);
if(nums[mid]==target)
{
if(mid==nums.size()-1||nums[mid+1]>target)//如果是邊界
{
return mid;

}
left=mid+1;//如果不是邊界縮小範圍
}
//二元搜尋法
if(nums[mid]<target)
{
left=mid+1;
}
if(nums[mid]>target)
{
right=mid-1;
}

}
return -1;
}
};
- 圖片
- 解題時間:1.5小時
- 自己完成程度:GOOLE解題思路，程式碼靠自己
- 解題思路:分別使用兩次二元搜尋法，一次找左端點，一次找右端點
- 關鍵在於遇到目標=中間值時，需要判斷他是否是左端點
- 如果mid==0||nums[mid-1]<target，代表mid到達了邊界或著mid的左邊已經沒有目標
，也就是左端點找到了!
- 如果還沒找到左端點，則繼續往左找，將上限縮小
- 目標!=中間值時，做法與二元搜尋法相同

- 判斷是否是右端點與上述概念相同
- 關鍵在於遇到目標=中間值時，需要判斷他是否是右端點
- 如果mid==nums[size]-1||nums[mid+1]>target，代表mid到達了邊界或著mid的右邊已經沒有目標
，也就是右端點找到了!
- 如果還沒找到右端點，則繼續往右找，將下限縮小
- 目標!=中間值時，做法與二元搜尋法相同
## 5.猜數字遊戲

題目：提供一個guess(int n)函式讓你呼叫來猜數字，當
你猜的數字過大時，guess()回傳 -1
你猜的數字過小時，guess()回傳 1
你猜的數字對時，guess()回傳 0

- 程式碼

    class Solution {
    public:
        int guessNumber(int n) {
         int left=1; int right=n;        
         while(left<=right)
        {
         int mid=int(left+(right-left)/2);
         int temp=guess(mid);    
         if(temp==0)//猜中了
         {
          return mid;
         }

         if(temp==-1)//猜的數字太大
         {
             right=mid-1;
         }
         else if(temp==1)//猜的數字太小
         {
             left=mid+1;
         }
          }
            return -1;
        }
    };
- 圖片
![](https://i.imgur.com/tbnlbJd.png)
- 解題時間:15分鐘
- 自己完成程度:靠自己
- 解題思路:用二元搜尋法
## 6.學習心得
本周的教學影片講解非常清晰，都聽得懂，本周作業明顯比上周還困難，前面兩題程式題都花費非常久的時間，一開始都沒甚麼頭緒，最後一題就相對簡單，雖然這次作業有減少但是花的時間好像沒有改變，希望自己能有所進步!