C++ Binary Search
See my latest update in repo LeetCode\n\n## Solution 1. Binary Search\n\nIntuition: Sort the array A. For each A[i], we can binary search A[p] >= (k - 1) * A[i]
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Binary Search\n\n**Intuition**: Sort the array `A`. For each `A[i]`, we can binary search `A[p] >= (k - 1) * A[i]` and `A[q] >= k * A[i]`, then all numbers `A[j]` with index in range `[p, q)` has `floor(A[j] / A[i]) = k - 1`.\n\n**Algorithm**: \n\n1. Sort the array `A`. \n1. For each `A[i]`, first count the duplicate of `A[i]`. If we have `dup` duplicates, then they will add `dup^2` to the answer.\n1. For the first `A[j] > A[i]`, let `div = A[j] / A[i]`, we use binary search to find the first `A[next] >= A[i] * (div + 1)`, then numbers `A[t]` where `t` is in `[j, next)` will have `floor(A[t] / A[i]) = div`. These numbers will add `(next - j) * div * dup` to the answer.\n\n```cpp\n// OJ: https://leetcode.com/problems/sum-of-floored-pairs/\n// Author: github.com/lzl124631x\n// Time: O(?)\n// Space: O(1)\nclass Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& A) {\n        long mod = 1e9 + 7, N = A.size(), ans = 0;\n        sort(begin(A), end(A));\n        for (int i = 0; i < N; ) {\n            long j = i + 1;\n            while (j < N && A[j] == A[j - 1]) ++j; // skip the duplicates of `A[i]`\n            long dup = j - i;\n            ans = (ans + dup * dup % mod) % mod; // the `dup` duplicates add `dup * dup` to the answer\n            while (j < N) {\n                long div = A[j] / A[i], bound = A[i] * (div + 1);\n                long next = lower_bound(begin(A) + j, end(A), bound) - begin(A); // find the first number `A[next] >= A[i] * (div + 1)`\n                ans = (ans + (next - j) * div % mod * dup % mod) % mod; // Each A[t] (j <= t < next) will add `div * dup` to the answer.\n                j = next;\n            }\n            i += dup;\n        }\n        return ans;\n    }\n};\n```
[]