Truly Binary Search, not Two Pointers
Intuition\nWhen we sort input array we\'d need to find for each item the pair which in sum with current one is less than target. Having array sorted means we ca
# Intuition\nWhen we sort input array we\'d need to find for each item the pair which in sum with current one is less than target. Having array sorted means we can apply binary search to quickly identify the right most element which satisfies the formula: `nums[i] + nums[j] < target`.\n\nLet\'s review first example. After sorting will get `[-1,1,1,2,3]`. So for first element which is `nums[0] = -1` we should find right most element which is sum with the current one is smaller than target.\n```\ni = it\'s current position\ngood = item which satisfies condition\nbad = sum is >= target\n           *\n[i,good,good,bad,bad]\n[-1,  1,   1,   2,  3]\n```\n\n# Approach\n1. Sort input array.\n2. Start iterating from the left most element.\n2.1. For each element find the difference between target and current one `target - nums[i]`\n2.2. Run Binary Search to find right most element which is smaller than `target-nums[i]`\n2.3. Add distance between curr element and result of BS to answer.\n3. Return total count for all pairs.\n\n# Complexity\n- Time complexity:\nTime complexity of O(n*log(n)) due to sorting and the binary search for each element.\n\n- Space complexity:\nO(1) - constant space complexity.\n\n# Code\n```javascript []\n/**\n * @param {number[]} nums\n * @param {number} target\n * @return {number}\n */\nvar countPairs = function(nums, target) {\n    nums.sort((a, b) => a - b);\n    const n = nums.length;\n    let result = 0;\n\n    for (let i = 0; i < n - 1; i++) {\n        // Use binary search to find the rightmost index where nums[i] + nums[j] < target\n        const lastValid = bs(nums, target-nums[i], i, n);\n        \n        // All indices from i to left will form valid pairs with nums[i]\n        result += lastValid - i;\n    }\n\n    return result;\n};\n\nfunction bs(nums, target, left, right) {\n        while ((right-left) > 1) {\n            const mid = left + Math.floor((right - left) / 2);\n\n            if (nums[mid] < target) {\n                left = mid;\n            } else {\n                right = mid;\n            }\n        }\n\n        return left;\n    }\n\n```
['Array', 'Binary Search', 'JavaScript']