###### tags: `演算法作業`
# 演算法作業 HW02
## 觀念題
### 1. 
- 

### 2. 
- 

## 程式題(延續二元搜尋)
### 3. 數列被轉置(LeetCode 33)
- 程式碼 :

class Solution { 
public:
    int search(vector<int>& nums, int target) {
        int left = 0,right = nums.size()-1;
        int mid = 0;
        while(left <= right){
            mid = left + (right-left)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] > nums[right]){
                //最左數到中間數為升序
                if(nums[mid] > target && nums[left] <= target){
                    right = mid -1;
                }else{
                    left = mid +1;
                }
            }else{
                //nums[mid] < nums[right]
                //中間數到最右數為升序
                if(nums[mid] < target && nums[right] >= target){
                    left = mid +1;
                }else{
                    right = mid -1;
                }
            }
        }
        return -1;
    }
};

- 測試輸出輸入的畫面 : 

- 花費的時間 : 1 **hr** 50 **min**
- 完成的程度 : 解題思路完全靠自己想，Test完後輸出結果錯誤，上網找哪裡想法錯誤，發現沒有考慮如果最左值或最右值是Target會怎麼樣。
- 解題思路 :
- 數列旋轉仍有序(不確定中點前或中點後)
- 二分關鍵 獲得中間值 決定向左向右
-  
- 發現中間數大於最右數，最左數到中間數為升序。
(中間數大於最左數也可 但中間數"可能等於"最左數")
- 如果中間數 == Target，return mid
- 如果中間數 < Target，left = mid +1
- 如果中間數 > Target，需判斷最左數
- 若最左數 <= Target，right = mid-1
- 若最左數 > Target，left = mid+1

- 發現中間數小於最右數，中間數到最右數為升序。
(中間數小於最左數也可 但中間數"可能等於"最左數")
- 如果中間數 == Target，return mid
- 如果中間數 < Target，需判斷最右數
- 若最右數 <= Target，left = mid+1
- 若最右數 > Target，right = mid-1
- 如果中間數 > Target，right = mid-1

### 4. 數字可能重複，回傳範圍(LeetCode 34)
- 程式碼 :

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        ans.push_back(preSearch(nums, target));
        ans.push_back(postSearch(nums, target));
        return ans;
    }
    
    int preSearch(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size()-1;
        int mid =0;
        if(nums.size() == 0){
            return -1;
        }
        while(left < right){
            mid = left + (right-left)/2;
            if(nums[mid] >= target){
                right = mid;
            }else{
                left = mid +1;
            }
        }
        if(nums[left] == target){
            return left;
        }else{
            return -1;
        }
    }
    int postSearch(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size()-1;
        int mid =0;
        if(nums.size() == 0){
            return -1;
        }
        while(left < right){
            mid = left + (right-left)/2 +1;
            if(nums[mid] <= target){
                left = mid;
            }else{
                right = mid -1;
            }
        }
        if(nums[left] == target){
            return left;
        }else{
            return -1;
        }
    }
};

- 測試輸出輸入的畫面 : 

- 花費的時間 : 10 **min**
- 完成的程度 : 完全靠自己
- 解題思路 :
- 雖然有重複 但是按照大小排列
- 可聯想到 **演算法作業 HW01 第3題**
- 中間值"可能"會等於left 所以在postSearch中間值需加1 否則會陷入迴圈
- 數字可能為null，先判斷長度是否為0，若是直接回傳-1。
### 5. 猜數字遊戲(LeetCode 374)
- 程式碼 :

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */
 /** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

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

- 測試輸出輸入的畫面 : 

- 花費的時間 : 10 **min**
- 完成的程度 : 完全靠自己
- 解題思路 :
- 終極密碼 二分法
- guess(num)
- return -1 ,比mid 小,right = mid -1;
- return 1 ,比mid 大,left = mid +1;
- return 0 ,成功猜中,return mid;

## 心得
### 6. 請寫下對於本週影片教學和程式作業的適應程度與喜惡。
- 老師講得很明白，我也完全可以聽懂。
- 第3題想了好久(大概有1hr在畫那張圖找規律)，曾試過找中間值左右兩邊會有固定的規律，後來發現按照升冪排序找到規律，最後找到規律還是很有成就感。相比第3題 4.5簡單許多。
- 還蠻適應的，第3題沒有特別找到更好的方法