# 演算法導論 HW2
https://hackmd.io/@wang1234/rJuXK-R15
## 1. 
| f(n) = O(g(n)) ≤ c×g(n) | 令c為最大項的常數值加1 |
| -------- | -------- |

f(n)=3n³-5n+6 ⇒ 1n³+1n+1 ⇒ <font color="DeepSkyBlue">O(n³)</font>

f(n)=3n³-5n+6 ⇒ <font color="DeepSkyBlue">c=3+1=4</font>

f(n)=3n³-5n+6 ≤ 4n³
⇒ -5n+6 ≤ n³
⇒ n ≥ 1 ⇒ <font color="DeepSkyBlue">n₀=1</font>

## 2. 
f(n)=2n²-100n-50 ⇒ 1n²+1n+1 ⇒ <font color="DeepSkyBlue">O(n²)</font>

f(n)=2n²-100n-50 ⇒ <font color="DeepSkyBlue">c=2+1=3</font>

f(n)=2n²-100n-50 ≤ 3n²
⇒ -100n-50 ≤ n²
⇒ n ≥ 1 ⇒ <font color="DeepSkyBlue">n₀=1</font>

## 3. 數列被轉置
[33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/description/)
解題思路:

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

花40分鐘，完全靠自己

## 4. 數字可能重複，回傳範圍
[34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
解題思路:

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

花40分鐘，完全靠自己

## 5. 猜數字遊戲
[374. Guess Number Higher or Lower](https://leetcode.com/problems/guess-number-higher-or-lower/)
<font color="Black">
解題思路:
> 數字的範圍在1到n,所以初始時左邊界為1,右邊界為n,
> 然後在while迴圈中,
> 如果將mid傳入guess的回傳值等於-1,表示pick(猜數字遊戲的答案)小於mid;
> 如果將mid傳入guess的回傳值等於1,表示pick(猜數字遊戲的答案)大於mid;
> 否則,當guess(mid)回傳0,此時,mid就是答案
</font>

class Solution(object):
    def guessNumber(self, n):
        left, right = 1, n
        while left <= right:
            mid = (left + right) // 2
            if guess(mid)==-1:
                right = mid - 1
            elif guess(mid)==1:
                left = mid + 1
            else:
                return mid 

花10分鐘，完全靠自己

## 6. 找出正數或負數的數量較大者
[2529. Maximum Count of Positive Integer and Negative Integer](https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer/)
<font color="Black">
解題思路:
> 找出正負數的交界,即找0或找0該插入的位置
> 
</font>

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

花30分鐘，完全靠自己

## 7. 心得
題目難度還行,但除了依著自己習慣的思路想到的寫法以外,是否能有其他更好的做法,沒什麼概念和感覺