# Binary search topic

# 704. Binary Search
## Question: (Easy)
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
## Solution: C++

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

## Notes
單純的binary search

---

# 74. Search a 2D Matrix
## Question: (Medium)
You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.
## Solution: C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row_num = matrix.size();
        int col_num = matrix[0].size();
        int start = 0;
        int end = (row_num*col_num)-1;
        while(start<=end){
            int mid = (start+end)/2;
            if(target>matrix[mid/col_num][mid%col_num]){
                start = mid+1;
            }
            else if(target<matrix[mid/col_num][mid%col_num]){
                end = mid-1;
            }
            else{
                return true;
            }
        }

        return false;
    }
};

## Notes:
雖然題目說是2-d matrix，但其實做法跟1-d binary search一樣，要把mid轉換成2-d的index即可。

# 875. Koko Eating Bananas
## Question: (Medium)
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4
Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23
## Solution: C++

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        long long int start = 1;
        long long int end = *max_element(piles.begin(), piles.end());
        int mid = -1; long long int sum = -1;
        int minima = end;
        while(start<=end){
            mid = (end-start)/2 + start;
            sum = 0;
            for(int i=0; i<piles.size(); i++){
                //cout<<piles[i]<<" "<<mid<<endl;
                sum+=(piles[i]/mid);
                if(piles[i]%mid!=0)
                    sum++;
            }
            //cout<<mid<<" "<<sum<<endl;
            if(sum>h){
                start=mid+1;
            }
            else if(sum<=h){
                end=mid-1;
                minima = min(mid, minima);//important
            }
        }
        return minima;
    }
};

## Notes:
Binary search的應用，search的對象為k，初始的時候start=1, end=max(piles)

---
# 2300. Successful Pairs of Spells and Potions
## Question (Medium)
You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.
Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful.
Thus, [2,0,2] is returned.
## Solution (C++)

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> ans(spells.size());
        sort(potions.begin(), potions.end());
        for(int i=0; i<spells.size(); i++){
            int start = 0, end = potions.size()-1;
            int mid = 0, prev_mid = -1;
            long long temp;
            while(start<=end){
                if((start+end)%2==1)
                    mid = 1 + (start+end)/2;
                else
                    mid = (start+end)/2;
                temp = (long long)spells[i]*(long long)potions[mid];
                if(temp>=success){
                    end = mid - 1;
                    prev_mid = mid;
                }
                else if(temp<success){
                    start = mid+1;
                }
                if(!(start<=end))
                    break;
            }
            ans[i] = ((prev_mid==-1)?0:(potions.size()-prev_mid));
            
        }
        return ans;
    }
};

## Notes
* binary search，如果mid的數值>success的話就紀錄起來
* 後續要判斷有幾個element>success的話，只需要index相減即可

---
# 162. Find Peak Element
## Question (Medium)
A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
## Solution (C++)

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size()==1)
            return 0;
        int start = 0, end = nums.size()-1; 
        int mid = 0;
        int peak_index = 0;
        while(start<=end){
            mid = (start+end)/2;
            if(mid==0){
                if(nums[mid]<=nums[mid+1]){
                    peak_index = mid+1;
                }
                else if(nums[mid]>=nums[mid+1]){
                    peak_index = mid;
                }
                break;
            }
            else if(mid==nums.size()-1){
                peak_index = mid;
                break;
            }
            else{
                if(nums[mid]<=nums[mid+1]&&nums[mid]>=nums[mid-1]){
                    start = mid+1;
                }
                else if(nums[mid]>=nums[mid+1]&&nums[mid]<=nums[mid-1]){
                    end = mid-1;
                }
                else if (nums[mid]>=nums[mid+1] && nums[mid]>=nums[mid-1]){
                    peak_index = mid;
                    break;
                }
                else{
                    start = mid+1;
                }
            }
        }
        return peak_index;
    }
};

## Notes:
* 我們這題是對**index**做binary search.
* 假設目前是選index這個位置，我們僅需考慮index+1, index-1，判斷這三個位置的狀態，是遞增or遞減or山峰or倒山峰
* 程式碼應該可以更簡潔化，但是我懶