# Leetcode 刷題筆記
###### tags: `LeetCode`
# [#35 Search insert position](https://leetcode.com/problems/search-insert-position/)

* 基本上就是經典的 Binary Search 問題，但碰到了一些基本問題我想要打在上面：
* `int mid = (left - right) / 2` 這條在最開始的binary search 不會有任何問題，但在其他binary Search 上必須要改成 `left + (right - left) = right`
* binary Search 會有紀錄值分為： left 跟 right
* 這一題的constrain 為：
* 陣列中的數字都唯一，不需要考慮重複性
* 也是因為這個constrain，讓我們在二元查找的時候可以在找不到的時候 `return left` 即可
* code 如下：

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

    }
};

# [#852 Peak index in a Mountain Array](https://leetcode.com/problems/peak-index-in-a-mountain-array/)

* 甚麼是 Mountain Array呢？以下為部分限定條件：
* array 的大小必須要大於等於 3
* 存在一個 `i` 使得 `arr[0] < arr[1] ... arr[i] > arr[i + 1] ... arr[arr.size() - 1]`
* 像一個山一樣
* 這個問題要求在 log(n) 的時間內找到這個山的頂點
* 假設 [0 1 0] ， 那這個山的頂點位置就會在 arr[1] 的位置

:::success
## 解題思路：
> 由於這題已經給好，array 一定會先遞增再遞減
> 那就可以利用爬山的方式：
>> 首先找出 mid = left + (right - left) / 2
>> 再來觀察他左右兩邊哪邊比較大要往哪裡走，所以必須要找出 mid - 1 跟 mid + 1
>> 如果都比自己小的話，那就會是頂點，如果有哪一邊比較大的話，就往哪邊走
:::

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // check if the peak is located behind and start
        if(arr[0] > arr[1])
            return 0;
        else if(arr[arr.size() - 1] > arr[arr.size() - 2])
            return arr.size() - 1;
        // 如果山峰在最前面或最後面的話就不用找
        int left = 0, right = arr.size() - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(arr[mid - 1] < arr[mid] && arr[mid] >arr[mid + 1]){
                return mid;
            }
            else if(arr[mid - 1] < arr[mid + 1]){
                left = mid;
            }
            else
                right = mid;
        }
        return 0;
    }
};