5. Sorting and Searching

1. Merge Sorted Array

https://leetcode.com/explore/interview/card/top-interview-questions-easy/96/sorting-and-searching/587/

merge sort:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = 0; i < n; i++){
            nums1[m+i] = nums2[i];
        }
        //sort(nums1.begin(), nums1.end());
        mergeSort(nums1);
    }
private: 
    void merge(vector<int>& arr, int l, int m, int r){
        int n1 = m - l + 1;
        int n2 = r - m;
        vector<int> L;
        vector<int> R;
        for(int i = l; i < m + 1; i++){
            L.push_back(arr[i]);
        }
        for(int j = m+1; j < r + 1; j++){
            R.push_back(arr[j]);
        }
        int l_p = 0, r_p = 0, c_p = l;
        while(l_p < n1 && r_p < n2){
            if(L[l_p] <= R[r_p]){
                arr[c_p] = L[l_p];
                c_p++;
                l_p++;
            } else {
                arr[c_p] = R[r_p];
                c_p++;
                r_p++;
            }
        }
        while(l_p < n1){
            arr[c_p] = L[l_p];
            c_p++;
            l_p++;
        }
        while(r_p < n2){
            arr[c_p] = R[r_p];
            c_p++;
            r_p++;
        }
    }
    void mergeSort(vector<int>& arr, int l, int r){
        if(l < r){
            int m = l + (r - l) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
    void mergeSort(vector<int>& arr){
        int n = arr.size();
        mergeSort(arr, 0, n - 1);
    }
};

merge sort with erase vector.begin():

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = 0; i < n; i++){
            nums1[m+i] = nums2[i];
        }
        //sort(nums1.begin(), nums1.end());
        mergeSort(nums1);
    }
private: 
    void merge(vector<int>& arr, int l, int m, int r){
        vector<int> L;
        vector<int> R;
        for(int i = l; i < m + 1; i++){
            L.push_back(arr[i]);
        }
        for(int j = m+1; j < r + 1; j++){
            R.push_back(arr[j]);
        }
        int c_p = l;
        while(L.size() > 0 && R.size() > 0){
            if(L[0] <= R[0]){
                arr[c_p] = L[0];
                L.erase(L.begin());
                c_p++;
            } else {
                arr[c_p] = R[0];
                R.erase(R.begin());
                c_p++;
            }
        }
        while(L.size() > 0){
            arr[c_p] = L[0];
            L.erase(L.begin());
            c_p++;
        }
        while(R.size() > 0){
            arr[c_p] = R[0];
            R.erase(R.begin());
            c_p++;
        }
    }
    void mergeSort(vector<int>& arr, int l, int r){
        if(l < r){
            int m = l + (r - l) / 2;
            mergeSort(arr, l, m);
            mergeSort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
    void mergeSort(vector<int>& arr){
        int n = arr.size();
        mergeSort(arr, 0, n - 1);
    }
};

2. First Bad Version

https://leetcode.com/explore/interview/card/top-interview-questions-easy/96/sorting-and-searching/774/

binary search:

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        return firstBadVersion(1, n, n);
    }
private:
    int firstBadVersion(int l, int r, int n){
        if(l < r){
            int m = l + (r - l) / 2;
            if(!isBadVersion(m))
                return firstBadVersion(m+1, r, n);
            else if(isBadVersion(m)){
                return firstBadVersion(l, m, n);
            }
        }
        return l;
    }
};