Created
November 13, 2024 14:18
-
-
Save hassam7/1c973360b6c50e036e6c2bb174df3607 to your computer and use it in GitHub Desktop.
binary search.js
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function countFairPairs(nums, lower, upper) { | |
| let n = nums.length; | |
| let count = 0; | |
| nums.sort((a, b) => a - b) | |
| for (let i = 0; i < n; i++) { | |
| let lowerIndex = lowerBound(nums, lower - nums[i], i + 1, n - 1); | |
| let upperIndex = upperBound(nums, upper - nums[i], i + 1, n - 1); | |
| count += upperIndex - lowerIndex; | |
| } | |
| return count; | |
| } | |
| function lowerBound(arr, x, start = 0, end = arr.length - 1) { | |
| let low = start, high = end; | |
| let ans = end + 1; | |
| while (low <= high) { | |
| let mid = Math.floor((low + high) / 2); | |
| if (arr[mid] >= x) { | |
| ans = mid; | |
| high = mid - 1; | |
| } else { | |
| low = mid + 1; | |
| } | |
| } | |
| return ans; | |
| } | |
| function upperBound(arr, x, start = 0, end = arr.length - 1) { | |
| let low = start, high = end; | |
| let ans = end + 1; | |
| while (low <= high) { | |
| let mid = Math.floor((low + high) / 2); | |
| if (arr[mid] > x) { | |
| ans = mid; | |
| high = mid - 1; | |
| } else { | |
| low = mid + 1; | |
| } | |
| } | |
| return ans; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment