7.18 （63）查找 & subsets二进制法~

to do

2] Search Insert Position

    int searchR (vector<int>& nums, int l, int r, int target) {
        if (l==r-1 || l==r) {
            if (target <= nums[l]) return l;
            else if (nums[r] == target || (nums[l] < target && target <nums[r])) return r;
            else if (nums[r] < target) return r+1;
        } 
        int mid = (l+r)/2;
        if (nums[mid]<target) return searchR(nums, mid, r, target);
        else if (target<nums[mid]) return searchR(nums, l, mid, target);
        else return mid;
    }
    
    int searchInsert(vector<int>& nums, int target) {
        if (nums.empty()) return 0;
        return searchR(nums, 0, nums.size()-1, target);
    }

3] Search a 2D Matrix

ncols, nrows自己都记反了，多练养成自己的惯例

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        
        int nrows = matrix.size(), ncols = matrix[0].size();
        int l=0, r=ncols * nrows-1;
        while (l<r) {
            int mid = (l+r)/2;
            int curr = matrix[mid/ncols][mid%ncols];
            if (curr<target) l = mid+1;
            else if (curr>target) r = mid-1;
            else return true;
        }
        return l==r? matrix[l/ncols][l%ncols]==target : false; 
    }

4] Subsets

1. recursion
   好吧其实要求有序的话，sort input once

    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return vector<vector<int>> {{}};
        int curr = nums.back();
        nums.pop_back();
        
        vector<vector<int>> lastSets = subsets(nums);
        int size = lastSets.size(); 
        for (int i=0; i<size; ++i) {
            vector<int> newSet = lastSets[i];
            newSet.push_back(curr);
            lastSets.push_back(newSet);
        }
        return lastSets;
    }

2. iteration

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret{{}};
        if (nums.empty()) return ret;
        
        // each iteration add all vectors of length i+1, ending w/ nums[i]
        for (int i=0; i<nums.size(); ++i) {
            // iterate through inserted vectors of length i
            int insertedSize = ret.size();
            for (int j=0; j<insertedSize; ++j) {
                vector<int> newv = ret[j];
                newv.push_back(nums[i]);
                ret.push_back(newv);
            }
        }
        
        return ret;
    }

还有二进制法，以后来看