# 演算法 二元搜尋法（續）

## :book: 第1題:

複雜度=$O( n$^3^$)$
$c=4$
$3n$^3^$-5n+6<=4n$^3^
$n$^3^$>=-5n+6$
$n$^3^$+5n>=6$
$n(n$^2^$+5)>=6$
$n$^2^$+5>=6$ or $n>=6$
$n>=1$

| $n$ | $f(n)=3n$^3^$-5n+6$ | $cg(n)=4n$^3^ |
| -------- | -------- | -------- |
| 1 | 4 | 4 |
| 2 | 20 | 32 |
| 3 | 72 | 108 |

$c=4$
$n_0$$=1$

---

## :book: 第2題：

複雜度=O( n^2^ )
c=3;
$2n$^2^$-100n-50<=3n$^2^
$n$^2^$>=-100n-50$
$n$^2^$+100n+50>=0$
$n>=1$

| $n$ | $f(n)=2n$^2^$-100n-50$ | $cg(n)=3n$^2^ |
| --- |:----------------------:| -------------:|
| 1 | $\|-148\|=148$ | 3 |
| 2 | $\|-242\|=242$ | 12 |
| 3 | $\|-332\|=332$ | 27 |
| 4 | $\|-418\|=418$ | 48 |
| 5 | $\|-500\|=500$ | 75 |
| 10 | $\|-850\|=850$ | 300 |
| 15 | $\|-1100 \|=1100$ | 675 |
| 20 | $\|-1250\|=1250$ | 1200 |
| 21 | $\|-1268\|=1268$ | 1323 |
| 23 | $\|-1292\|=1292$ | 1587 |

$c=3$
$n_0$$=21$

---

## :book:第3題：數列被轉置 leetcode 33
* 花費時間：約2小時
* 自己完成程度：完全靠自己
* 思路：

先設定一個新的動態陣列sortedNums，這個是用來儲存排序後的nums，因為已知nums有可能會旋轉i個，如果不排序是沒辦法套用二元搜尋的。

排序之後會有2個情況：有旋轉與沒旋轉
如果沒旋轉的話，我們的location（用於儲存旋轉的數量i）就等於0

有旋轉的話，我們就用一個for迴圈找到sortedNums的第一個數字（也就是最小數字）究竟出現在原本陣列的哪一個位置，然後丟給location，這樣就找到了旋轉的數量。
這一步驟我有試過把for迴圈改成二元搜尋法，然後我寫不出來，我好廢。

然後就可以開始愉快的套用2元搜尋法，不過搜尋的陣列是用已排序的。

找到了目標數字的位置後，精髓來了，因為我們需要知道的是目標數字在原本陣列的位置，而不是排序後的位置

我們可以把原陣列看成一個循環
【4,5,6,7,0,1,2】->【2,4,5,6,7,0,1】->【1,2,4,5,6,7,0】->【0,1,2,4,5,6,7】->【7,0,1,2,4,5,6】.....

那我們就可以用cycle queue的概念來看這個情況
我們知道任何數字用mod之後 就會被限定在一個範圍內 那我們的location就是用來表示我前面需要空幾個位置 然後再開始計算位子
那我們怎麼知道我們取餘的數字是多少，因為我們的陣列都是塞滿資料的，那就是直接取陣列裡面有多少個數字就好

我們要做的就是 把留空的位數加上我們在排序後的陣列所得到的數字 去取餘數
於是就得出了(location + middle) % nums.size()這樣的算式

以測資來說 假設我們現在要找的數字是0，那我們的for迴圈取到的location會是4，那我們在排序後的陣列取到目標數字的位子是0

（0+4）%7=4
也就是會變成這樣

那我們有用mod來限制位子 然後讓他形成一個cycle 就變成下面這樣

location的目的就是用來留空前面的格子 再加上排序後的目標位子，就得出目標數字在原陣列中的index了。

* 程式碼：

#include"iostream"
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        vector<int>sortedNums = nums;
        sort(sortedNums.begin(), sortedNums.end());
        int location = 0;
        int resultIndex = -1;
        if (sortedNums[0] != nums[0])
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (sortedNums[0] == nums[i])
                {
                    location = i;
                    break;
                }
            }
        }
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right)
        {
            int middle = left + (right - left) / 2;
            if (sortedNums[middle] == target)
            {
                resultIndex = ((location + middle) % nums.size());
                break;
            }
            else if (sortedNums[middle] < target)
            {
                left = middle + 1;
            }
            else if (sortedNums[middle] > target)
            {
                right = middle - 1;
            }
        }

        return resultIndex;

    }
};

int main()
{
    Solution a;
    vector<int> nums = {7,8,1,2,3,4,5,6 };
    int target = 2;
    int aa = a.search(nums, target);
    cout << aa;

}

* 通過截圖

---

## :book: 第4題：數字可能重複，回傳範圍 leetcode 34

* 花費時間：約1小時半
* 自己完成程度：完全靠自己
* 思路：
題目需要找到指定重複的數字的最開始位置與結束位置，最一開始我看錯題目，以為要輸出全部數字的位置，寫了大概半小時才發現原來只需要頭尾。
我第一次的方式是先找到目標數字的最前面的位置，然後用for迴圈把接下來到結束的位置pushback到vector裡面，然後再回傳，之後發現看錯了之後，我就只是把那個for迴圈改成從目標位置往前以及往後擴散找到最前與最後，可是這樣的方式我覺得會跑很慢，所以我就用兩個二元搜尋，一次是找到最前面，第二次是找到最後面。
* 程式碼：

#include"iostream"
#include<vector>
#include<algorithm>
using namespace std;

class Solution
{
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int left=0;
        int right = nums.size() - 1;
        int front=-1;
        int back=-1;
        while (left <= right &&nums.size()>0)
        {
            int middle = left + (right - left) / 2;
            if (nums[middle] == target)
            {
                if (middle <= 0 || nums[middle - 1] != target)
                {
                    front = middle;
                    break;
                }
                else
                {
                    right = middle - 1;
                }
            }
            else if (nums[middle] < target)
            {
                left = middle + 1;
            }
            else if (nums[middle] > target)
            {
                right = middle-1;
            }
        }
        if(front!=-1)left = front;
        right = nums.size()-1;
        while(left<=right && nums.size() > 0)
        {
            int middle = left + (right - left) / 2;
            if (nums[middle] == target)
            {
                if (middle >= nums.size() - 1 || nums[middle + 1] != target)
                {
                    back = middle;
                    break;
                }
                else
                {
                    left = middle + 1;
                }
            }
            else if (nums[middle] < target)
            {
                left = middle + 1;
            }
            else if (nums[middle] > target)
            {
                right = middle - 1;
            }
        }
        vector<int> output = { front,back };
        return output;
    }
};

int main()
{
    Solution a;
    vector<int> nums = {1  };
    int target = 3;
    vector<int> out = a.searchRange(nums, target);
    printf("[%d,%d]",out[0],out[1]);

}

* 通過截圖

---

## :book: 第5題：猜數字遊戲 leetcode 374

* 花費時間：約10分鐘
* 自己完成程度：完全靠自己
* 思路：
這題跟上禮拜的其中一題很像（作業5 最早出問題的版本）也是一樣用內建api來寫，在寫的過程中我被題目搞，因為題目的大於小於的判斷的定義，跟右邊寫程式那邊的註解給的定義不同，最一開始我用的是右邊註解的定義，試跑的時候一直錯，再仔細看題目才發現這個問題，哭啊。
* 程式碼：

class Solution 
{
public:
    int guessNumber(int n) 
    {
        int left=0;
        int right=n;
        while(1)
        {
            int middle=left+(right-left)/2;
            int temp=guess(middle);
            if(temp==-1)
            {
                right=middle-1;
            }
            else if(temp==1)
            {
                left=middle+1;
            }
            else return middle;
        }
    }
};

* 通過截圖

---

## :book: 第6題：請寫下對於本週影片教學和程式作業的適應程度與喜惡。

這次的作業我真的差一點就要去網路找答案了，還好我有堅持下來好好想要怎麼寫，這次的難度比起上禮拜難了很多，可是寫出來之後很爽。

###### tags: `演算法`