Binary Search | Intuition explained with example
Intuition\n Describe your first thoughts on how to solve this problem. \nIf we sort the potions array and find the minimum index where the product is greater th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf we sort the potions array and find the minimum index where the product is greater than or equal to success, then we can be sure that the rest of the potions array will give product greater than or equal to success only.\n\nTo solve this kind of problem, we can use Binary Search. We can search in the range 0 to potions.size() and update the range according to whether the mid-value is enough or not.\n\n![image.png](https://assets.leetcode.com/users/images/9b20c1e9-0b07-4d87-9031-9d9a79afb50e_1680414955.5710003.png)\n\nThe condition would be:\n``` \nspell[i]*potions[j]>=success\n=> potions[j]>=success/spell[i] (as success can be a large number)\n```\nNow we need to find the index where this condition is satisfied for the first time.\n# Example\nLet\'s say we have the following inputs:\n```\nspells = [2, 3, 4]\npotions = [1, 2, 3, 4, 5]\nsuccess = 5\n```\n\nAfter sorting potions, we have:\n```\npotions = [1, 2, 3, 4, 5]\n```\n\nFor num = spell[0] = 2, we call binary search. \n```\nsuccess/num = 2.5 \nThe index of the first element in potions that is >= 2.5 is 2.\nTherefore, we append size-idx = 5-2 = 3 to the ans vector.\n```\nFor num = 3:\n```\nsuccess/num = 1.67\nThe index of the first element in potions that is >= 1.67 is 1.\nTherefore, we append n-idx = 5-1 = 4 to the ans vector.\n```\n\nFor num = 4:\n```\nThe index of the first element in potions that is g>= 1.25 is 0.\nTherefore, we append n-idx = 5-0 = 5 to the ans vector.\n```\nThe final ans vector:\n```\n[3, 4, 5]\nindicating that there are 3 successful pairs for num = 2, \n4 successful pairs for num = 3, \nand 5 successful pairs for num = 4.\n```\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(mlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int binarySearch(int num, vector<int>& potions, long long success){\n        int left=0, right=potions.size()-1;\n        double curr=(double)success/num; \n        while(left<right){\n            int mid=left+(right-left)/2;\n            if(potions[mid]>=curr){ \n                right=mid;  // set right to mid to search for lower indices\n            }\n            else left=mid+1;  // else set left to mid+1 to search for higher indices\n        }\n        if(potions[right]>=curr) return right;  // if any element has product greater than or equal to success\n        else return -1;  // else potion with success probability not fount\n    }\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        vector<int>ans;\n        int n=potions.size();\n        sort(potions.begin(),potions.end()); \n        for(int num:spells){\n            int idx=binarySearch(num,potions,success);  // find index where condition is satisfied for the first time\n            if(idx==-1) ans.push_back(0);  // if potion with success probability not found, add 0\n            else  ans.push_back(n-idx);  // else, n-idx would be the number of pairs that satisfy the condition\n        }\n        return ans;  \n    }\n};\n\n```
['Binary Search', 'C++']