# 演算法作業二

## 觀念題

- 第1題: Prove $f(n) = 4n^3 - 5n + 6$
:::info
$f(n) >= 5n^3\space\forall\space n>=1$
so, $f(n) = O(n^3)$
Q.E.D.
:::

- 第2題: Prove $f(n) = 30n^2 - 100n -50$
:::info
$|f(n)| >= 31n^2\space \forall\space n>=3$
so, $f(n) = O(n^2)$
Q.E.D.
:::
- 第3題: Prove $f(n) = 5n^4 - 10n + 6$
:::info
$f(n) >= 6n^4 \space \forall \space n>=1$
so,$f(n) =O(n^4)$
Q.E.D.
:::

## 程式題

### 第三題：數列被轉置
[leetcode 33](https://leetcode.com/problems/search-in-rotated-sorted-array/)
- 程式碼
:::spoiler C++

	class Solution {
	public:
		int search(vector<int>& nums, int target) {
			int left  = 0;
			int right = nums.size()-1;

			while (left<=right){
				int mid = left + (right - left) / 2;

				if (target == nums[mid])
					return mid;

				if (nums[left] <= nums[mid]){
					// May Not Be Rotated
					if ( nums[left] <= target && target <= nums[mid] ){
						// target is in left to mid
						right = mid - 1;
					}
					else{
						//target is not in left to mid
						left = mid + 1;
					}

				}
				else{
					//May Not Rotated
					if ( nums[mid] <= target && target <= nums[right] ){
						// target is in mid to right
						left = mid + 1;
					}
					else{
						//target is not in mid to right
						right = mid - 1;
					}
				}
			}
			return -1;
		}
	};

:::
- 執行結果
- 程式語言：C++
- 花費時間：20分鐘
- 完成程度：有上網看思路
- ref 1 ：[ref](https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/3879263/100-binary-search-easy-video-o-log-n-optimal-solution)
- 思路：
1. 這題可能包含無旋轉的array
2. 所以我們可以簡單的把陣列拆成兩部分
:::info
###### 以測試資料1為例
- 將陣列分成兩個，**向左遞減與向右遞增**進行討論
:::
3. 判斷搜索範圍是否為**向左遞減與向右遞增**進如下
- 向右遞增：`nums[left] <= nums[mid]`
- 向左遞減：`nums[left] > nums[mid`
4. 最後，我們只要用二分搜的方式就可以求解了
- 向右遞增
- `target`是否在`[left...mid]`之間 => `right = mid -1`
- 否則 => `left = mid + 1`
- 向左遞減
- `target`是否在`[mid...rigjt]`之間 => `left = mid + 1`
- 否則 => `right = mid - 1`

### 第四題：數字可能重複，回傳範圍
[leetcode 34](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
- 程式碼
:::spoiler C++

	class Solution {
	public:
		vector<int> searchRange(vector<int>& nums, int target) {
			vector<int>ans(2);

			ans[0] = lowerBound(nums, target);
			ans[1] = upperBound(nums, target);

			return ans;
		}

	private:
		int lowerBound(vector<int>& nums, int target){
			int left  = 0;
			int right = nums.size() - 1;

			int ans = -1;
			while (left <= right){
				int mid = left + (right - left) / 2;

				if (nums[mid] < target){

					left = mid + 1;
				}
				else{
					right = mid - 1;
					ans   = mid;  
				}
			}
			if (ans == -1) return -1;
			return nums[ans] == target?ans:-1;
		}


		int upperBound(vector<int>& nums, int target){
		   int left  = 0;
			int right = nums.size() - 1;

			int ans = -1;
			while (left <= right){
				int mid = left + (right - left) / 2;

				if (nums[mid] <= target){

					left = mid + 1;
					ans   = mid;
				}
				else{
					right = mid - 1;

				}
			}
			if (ans == -1) return -1;
			return nums[ans] == target?ans:-1;
		}
	};

:::
- 執行結果
- 程式語言：C++
- 花費時間：10分鐘
- 完成程度：靠自己
- 思路
1. 這題跟上周題目很像，是求出lowerbound 跟 upperbound
2. 所以我會拿ans值迭代的紀錄可能的答案值
3. 最後回傳答案
### 第五題: 猜數字遊戲
[leetcode 374](https://leetcode.com/problems/guess-number-higher-or-lower/description/)
- 程式碼
:::spoiler C++

	class Solution {
	public:
		int guessNumber(int n) {
			int left = 1;
			int right = n;

			while(left<=right){
				int mid = left + (right - left) / 2;

				if (!guess(mid)){
					return mid;
				}
				else if (guess(mid) == 1){
					left = mid + 1;
				}
				else{
					right = mid - 1;
				}
			}
			return -1;
		}
	};

:::
- 執行結果
- 程式語言：C++
- 花費時間：5分鐘
- 完成程度：靠自己
- 思路：
- 這題高中就有稍微聽過類似的了，其實就是二分搜
- 分成幾個情況討論：
- 比猜的數字大：則`right = mid - 1`
- 跟猜的數字一模一樣，則`return mid`
- 比猜的數字小，則`left = mid + 1`
### 第六題: 找出正數或負數的數量較大者
[leetcode 2529](https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer/)
- 程式碼
:::spoiler C++

	class Solution {
	public:
		int maximumCount(vector<int>& nums) {
			int left = 0;
			int right = nums.size() - 1;

			int lower = lowerBound(nums,0);
			int upper = nums.size() - upperBound(nums,0);
			return std::max(lower,upper);
		}
	private:
		int lowerBound(vector<int>& nums, int target){
			int left  = 0;
			int right = nums.size() - 1;

			while (left <= right){
				int mid = left + (right - left) / 2;

				if (nums[mid] >= target){
					right = mid - 1;
				}
				else{
					left = mid + 1;
				}
			}

			return left;
		}


		int upperBound(vector<int>& nums, int target){
			int left  = 0;
			int right = nums.size() - 1;

			while (left <= right){
				int mid = left + (right - left) / 2;

				if (nums[mid] > target){
					right = mid - 1;
				}
				else{
					left = mid + 1;
				}
			}

			return left;
		}
	};

:::
- 執行結果
- 程式語言：C++
- 花費時間：20分鐘
- 完成程度：靠自己
- 思路：
~~話說我後來發現這題測資的測資用線搜還比較快~~
1. 這題跟第四題很像，都是找lowerBound與upperBound
2. 我們簡化題目
- 先找0的upperBound和lowerBound
- 再從剛剛的答案算出所求
3. 實際例子
:::info
###### 以測資一為例子
###### 以測資二為例
:::
- 這樣可以統整出
- $negaive = lower$
- $positive = size - upper$
4. 最後`return std::max(negative,Positive)`即可

## 心得
這周跟上周一樣都是二分搜，有幾題比較印象深刻，第三題跟最後一題，是我想最久的題目，我覺得那幾題有點抽象，我要拿紙筆推才解出來。

這周的課程在講時間複雜度，老實說之前計概有學過，但我到現在才知道原本的假設是$f(n)>=0$，我覺得蠻特別的o.O。