STANDARD BINARY SEARCH || C++
Intuition\n--items[i][0] indicates price and items[i][1] indicates beauty.\n--We want to return ans vector containing maximum beauty for particular query.\n--Th
# Intuition\n--items[i][0] indicates price and items[i][1] indicates beauty.\n--We want to return ans vector containing maximum beauty for particular query.\n--The query vector has list of prices for which we want to find maximum beauty from items.\n--The maximum beauty can be of a lower price.\n\nFor eg:- items = [[1,100], [2, 8]], query[1, 2] \nFor this our ans = [100, 100] as upto price 2 our maximum beauty is 100.\n\nSo for this we can precalculate the maximum value upto certain points.\nFor this purpose we will sort the items vector.\n\n# Approach\n1. Sort the items vector.\n2. Precalculate the maximum beauty for every price.\n3. Using standard binary search for optimally finding maximum beauty for each query.\n\n# Complexity\nm -> size of item vector, n -> size of query vector\n\n# Time complexity:-  \nO(mlogm)[Sorting]\nO(m)[Finding max Beauty before calculating ans]\nO(nlogm)[Binary Search for each query]\n\n\n### Overall Time Complexity :- \nO((n+m)logm)\n\n# Space Complexity:- \nO(n)[Storing ans]\n\n# Code\n```cpp []\n\n\nclass Solution {\npublic:\n\n    int binarySearch(vector<vector<int>>& items, int query){\n        \n        int n     = items.size();\n\n        int start = 0;\n        int end   = n - 1;\n\n        int ans = 0;\n\n        while(start <= end){\n            int mid = start + (end - start)/2;\n\n            if(items[mid][0] <= query){\n                ans = items[mid][1];\n                start = mid+1;\n            }\n            else{\n                end = mid - 1;\n            }\n        }\n\n        return ans;\n    }\n\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n\n        //Step1:- Sorting\n        sort(items.begin(), items.end());\n\n        //Step2: Precalculate maxBeauty \n        for (int i = 1; i < items.size(); i++) {\n            items[i][1] = max(items[i][1], items[i - 1][1]);\n        }\n\n>         //Stepr:- Finding our ans by B.S\n        int n = queries.size();\n        vector<int> maxBeauty(n, 0);\n\n        for(int i = 0; i < n; i++){\n            int temp = binarySearch(items, queries[i]);\n\n            maxBeauty[i] = temp;\n        }\n\n        return maxBeauty;\n        \n    }\n};\n\n//Please upvote**\n```
['Array', 'Binary Search', 'Sorting', 'C++']