# 演算法 二元搜尋法(binary search)

## 1.本週影片中提到的NP-complete問題有哪些？
### 0/1 Kanpsack Problem 打包問題


### Traveling Salesperson Problem 旅行推銷員問題


### Partition Problem 分割問題


### Art Gallery Problem 美術館問題


---

## 2.請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。

### Chromatic Number Problem 著色問題
* 給定一個圖 G = (V, E)，我們要為頂點 V 上色。
* 輸入：上色的原則是相鄰的兩個頂點 u, v，即 (u, v) ∈ E，必須著不同的顏色。
* 輸出： 是不是存在一種著色方法只使用 k 種顏色？。
---

## 程式題：二元搜尋(Binary Search)
* 花費時間：約11分鐘
* 自己完成程度：完全靠自己
* 程式碼：

#include"bits/stdc++.h"
using namespace std;

class Solution
{
public:
    int search(vector<int>& nums, int target)
    {
       int leftindex=0;
       int rightindex=nums.size()-1;
       int middleindex;
       while(leftindex<=rightindex)
       {
           middleindex=(leftindex+rightindex)/2;
           if(nums[middleindex]==target)return middleindex;
           else if (nums[middleindex]>target)rightindex=middleindex-1;
           else if(nums[middleindex]<target)leftindex=middleindex+1;
       }
       return -1;
    }
};



int main()
{
    vector<int> nums={-1,0,3,5,9,12};
    int target=9;

    Solution a;

    cout<<a.search(nums,target)<<endl;
}

* 通過截圖：

---

## 3.二元搜尋應用：當數字可以重覆
* 花費時間：約15分鐘
* 自己完成程度：完全靠自己
* 程式碼：

#include"bits/stdc++.h"
using namespace std;

class Solution
{
public:
    int search(vector<int>& nums, int target)
    {
       int leftindex=0;
       int rightindex=nums.size()-1;
       int middleindex;
       int tempindex=-1;
       while(leftindex<=rightindex)
       {
           middleindex=(leftindex+rightindex)/2;
           if(nums[middleindex]==target)
           {
               tempindex=middleindex;
               rightindex=middleindex-1;

           }
           else if (nums[middleindex]>target)rightindex=middleindex-1;
           else if(nums[middleindex]<target)leftindex=middleindex+1;
       }
       return tempindex;
    }
};



int main()
{
    vector<int> nums={1,6,6,7,8};
    int target=6;

    Solution a;
    int index=a.search(nums,target);
    cout<<index<<endl;
}

---

## 4.二元搜尋應用：找數字該插入的位置
* 花費時間：約15分鐘
* 自己完成程度：完全靠自己
* 程式碼：

#include"bits/stdc++.h"
using namespace std;

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

int main()
{
    Solution a;

    vector <int> nums={1,3,5,6};
    int target = 2;

    int ans=a.searchInsert(nums,target);
    cout<<ans<<endl;
}

* 通過截圖：

---

## 5.二元搜尋應用：找到最早出問題的版本
* 花費時間：約1小時
* 自己完成程度：完全靠自己
* 程式碼：

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

* 通過截圖：

---

## 6.二元搜尋應用：開根號後的整數部分
* 花費時間：約1小時
* 自己完成程度：完全靠自己
* 程式碼：

#include"iostream"
using namespace std;

int main()
{
    int target;
    while (cin >> target)
    {
        int left=0;
        int right=target;
        double middle;
        int last=0;
        int now;
        while (1)
        {
            if (target == 1)
            {
                last = 1;
                now = 1;
            }
            middle = (left + right)/ 2;
            double pow = middle * middle;
            if (pow > target)
            {
                right = middle - 1;
                now = middle;
            }
            else if (pow < target)
            {
                left = middle + 1;
                now = middle;
            }
            else
            {
                last = middle;
                now = middle;
            }
            if (now == last)break;
            else last = now;
        }
        cout << last;
    }
}

* 通過截圖：

---

## 7.本週心得

經過這第一次的上課影片，我知道了演算法的重要性，以前不管在計算機概論也好，抑或是朋友聊天的時候就有聽說過NP完備問題，當時其實也不以為然，結果豁然發現其實NP完備問題一直都在我們身邊，不管是打包問題還是分割問題，都是我們在現實中有可能會碰到的，打包問題很顯然是老師提到的行李箱，分割問題可能就是會出現在朋友之間分錢的時候。
作業方面，我個人覺得老師以基礎延伸出用途的做法相比起直接解題還來得有趣一點，畢竟我們可以清楚了解他可以實際使用的情況，而不是為了解題而學，也有可能我比較不喜歡解題。
線上上課方面，我還是覺得實體上課成效比較大，畢竟可以及時發問，在這點上，由於人的記憶力有限，又或者性格較為害羞內向，不敢在事後發問，怕老師覺得我們沒有認真看影片什麼的，就會讓有問題的學生退縮。
大家當然可以記錄下來遇到的問題然後再發問，單還是有學生會害羞。
大家當然可以上網自己搜尋，但網路上的資源太多太雜，眼花繚亂，也存在很多誤導的資料，這還不如直接問對這些問題清楚的老師。

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