find bound of value in an array

find-bounds.js

var Mocha = require('mocha')
var assert = require('assert')
var mocha = new Mocha()

// Bit of a hack, sorry!
mocha.suite.emit('pre-require', this, 'solution', mocha)

/*

Given a sorted array of integers
return the low and high index of the given key.
Return -1 if not found.
The array length can be in the millions with many duplicates.


[minIndex, maxIndex] = findBoundOfValueInArray(1, [1,2,3]);

*/


//0,1,2,[3],4,5,6,7,8,9
//0,10
//0,4
//3,4

//avg nlogn 
//worst n
//can be improved by using a recursive find for bounds 
const findBoundOfValueInArray = (valueToFind, array) => {
  //todo handle empty array;
  if(array.length === 0)
  {
    return 0;
  }
  
  const find = (valueToFind, array, lowerSearchBound, upperSearchBound) => 
  { 
    const midPoint = findMidPoint(lowerSearchBound, upperSearchBound);
    const valueAtMidPoint = array[midPoint];

    console.log(`lowerSearchBound:${lowerSearchBound} - upperSearchBound:${upperSearchBound} midPoint:${midPoint} valueAtMidPoint:${valueAtMidPoint} array:${array} find:${valueToFind}`);

    
    if(valueAtMidPoint === valueToFind)
    {
      return midPoint;
    }

    if(!valueAtMidPoint || lowerSearchBound == upperSearchBound)
    {
      return -1;
    }
    
    if(valueAtMidPoint > valueToFind)
    {
      return find(valueToFind, array, lowerSearchBound, midPoint-1);
    }else{
      return find(valueToFind, array, midPoint+1, upperSearchBound);
    }
  }

  const foundAtIndex = find(valueToFind, array, 0, array.length);
  if(foundAtIndex === -1)
  {
    return -1;
  }

  console.log(`found at index${foundAtIndex}`);

  let lowerBound = foundAtIndex; 
  for(let i = foundAtIndex-1; i >= 0; --i)
  {
    if(array[i] !== valueToFind)
    {
      lowerBound = i+1;
      break;
    }
  }

  let upperBound = foundAtIndex; 
  for(let i = foundAtIndex+1; i < array.length; ++i)
  {
    if(array[i] !== valueToFind)
    {
      upperBound = i-1;
      break;
    }
  }


  return [lowerBound, upperBound];
}

const findMidPoint = (lower, upper) => 
{
  return lower + Math.round((upper - lower) / 2);
}

// n 
const findBoundOfValueInArraySlow = (find, array) => {
  for(let i = 0; i < array.length; i++)
  {
    if(array[i] === find)
    {
      let upperBoundIndex = i;
      for(let j = i+1; j < array.length; j++)
      {
        if(array[j] === find)
        {
          ++upperBoundIndex;
        }else{
          return [i, upperBoundIndex]
        }
      }
    }
  }

  return -1;
}

describe('Find bounds of value', () => {
  it('should return correct min and max', () => {
    const result = findBoundOfValueInArray(1, [1,2,3]);
    assert.deepEqual([0,0], result);
  });
  it('should return correct min and max', () => {
    const result = findBoundOfValueInArray(3, [1,2,3,3,3,4,5,6,7,8,9]);
    assert.deepEqual([2,4], result);
  });

  it('should return -1 if not found', () => {
    const result = findBoundOfValueInArray(5, [1,2,3]);
    assert.equal(-1, result);
  });

  it('find midPoint of array', () => {
    assert.equal(findMidPoint(0, 5), 3)
    assert.equal(findMidPoint(5, 5), 5)
    assert.equal(findMidPoint(10, 15), 13)
    assert.equal(findMidPoint(0, 1), 1)
  });

});

mocha.run()