Busca binaria intervalo

interval-bsearch.js

function rightMostBSearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1; // Initialize result to -1 for the case when the target is not present

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);

    if (arr[mid] === target) {
      // middlekey is equal to the target - update the left pointer so it continue to find the right most key
      result = mid;
      left = mid + 1
    } else if (target < arr[mid]) {
      // if target is lesser than middle key - apdates the right pointer
      right = mid - 1;
    } else {
      // if target is greater than middle key - updates the left pointer
      result = mid; // since we are looking for keys greater o equal, we also update the result
      left = mid + 1;
    }
  }

  return result;
}

function leftMostBSearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = -1; // Initialize result to -1 for the case when the target is not present

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);

    if (arr[mid] === target) {
      // If the target is found, update the result and search to the left for the leftmost occurrence
      result = mid;
      right = mid - 1;
    } else if (arr[mid] < target) {
      // If the element at mid is less than the target, update left to search in the right half
      left = mid + 1;
    } else {
      // If the element at mid is greater than the target, update right to search in the left half
      result = mid; // Update result to the current mid
      right = mid - 1;
    }
  }

  return result;
}

module.exports = {
  leftMostBSearch,
  rightMostBSearch,
  intervalBSearch(array, [lowerKey, upperKey]) {
    const lowerIndex = leftMostBSearch(array, lowerKey);
    const upperIndex = rightMostBSearch(array, upperKey);

    if (lowerIndex === -1 || upperIndex === -1) return [];

    return array.slice(lowerIndex, upperIndex + 1);
  }
}

interval-bsearch.test.js

const { intervalBSearch, leftMostBSearch, rightMostBSearch } = require('./interval-bsearch');

describe('rightMostBSearch', () => {
  describe('when there are more keys', () => {
    it('finds the rightmost index', () => {
      const arr = [0, 1, 1, 1, 1, 3, 3, 3, 3, 4, 9];

      const index = rightMostBSearch(arr, 3);

      expect(index).toEqual(8);
    });
  });

  describe('when exact key is not present', () => {
    describe('when there are no lesser keys', () => {
      it('returns -1', () => {
        const arr = [2, 2, 4, 9];

        const index = rightMostBSearch(arr, 1);

        expect(index).toEqual(-1);
      });
    });

    describe('when there are lesser keys', () => {
      it('finds the index of the key lesser than the target', () => {
        const arr = [0, 1, 1, 1, 1, 1, 2, 2, 4, 9];

        const index = rightMostBSearch(arr, 10);

        expect(index).toEqual(9);
      });
    });
  });
});

describe('leftMostBSearch', () => {
  describe('when there are more keys', () => {
    it('finds the leftmost index', () => {
      const arr = [0, 1, 1, 1, 1, 3, 3, 3, 3, 4, 9];

      const index = leftMostBSearch(arr, 3);

      expect(index).toEqual(5);
    });
  });

  describe('when exact key is not present', () => {
    describe('when there are no greater keys', () => {
      it('returns -1', () => {
        const arr = [0, 1, 1, 1, 1, 1, 2, 2, 4, 9];

        const index = leftMostBSearch(arr, 10);

        expect(index).toEqual(-1);
      });
    });

    describe('when there are greater keys', () => {
      it('finds the index of the key greater than the target', () => {
        const arr = [0, 1, 1, 1, 1, 1, 2, 2, 4, 9];

        const index = leftMostBSearch(arr, 3);

        expect(index).toEqual(8);
      });
    });
  });
});

describe('intervalBSearch', () => {
  describe('when lower and upper bounds are found', () => {
    it('returns indexes', () => {
      const interval = intervalBSearch([2, 4, 6, 8, 10], [2, 6]);
      console.log({ interval })

      expect(interval).toEqual([2, 4, 6]);
    });
  });

  describe('when upper key is not found', () => {
    it('returns the nearest index of upper', () => {
      const interval = intervalBSearch([2, 4, 6, 8, 10], [3, 5]);

      expect(interval).toEqual([4]);
    })
  })

  describe('when lower key is not found', () => {
    it('returns the nearest index of lower', () => {
      const interval = intervalBSearch([2, 4, 6, 8, 10], [3, 6]);

      expect(interval).toEqual([4, 6]);
    })
  })

  describe('when any boundary is not found', () => {
    it.each([
      {lower: 8, upper: 6},
      {lower: 2, upper: 1},
      {lower: 11, upper: 11},
      {lower: -1, upper: 1},
    ])(`returns an empty array - interval => $lower,$upper`, ({lower, upper}) => {
      const interval = intervalBSearch([2, 4, 6, 8, 10], [lower, upper]);

      expect(interval).toEqual([]);
    });
  });
});