Skip to content

Instantly share code, notes, and snippets.

@hassam7

hassam7/binary search.js

Created November 13, 2024 14:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save hassam7/1c973360b6c50e036e6c2bb174df3607 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save hassam7/1c973360b6c50e036e6c2bb174df3607 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. hassam7 created this gist Nov 13, 2024.
    47 changes: 47 additions & 0 deletions binary search.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,47 @@
    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;
    }