Binary search that gets ALL matching results

Question

I am implementing a binary search to retrieve all matches of a specified value. Instead of a regular binary search that would just return the first match, I want to get that first match AND all matches above and below it in the set of objects.

For example, I have an array of objects that are sorted by the name property of each object in alphabetical order, and the first letter of that name property is what I use for comparison of the value provided.

The object would look like this (using fake values):

[
    { name: 'Apple',      id: 1, ...},
    { name: 'Apple',      id: 2, ...},
    { name: 'Basketball', id: 3, ...},
    { name: 'Basketball', id: 4, ...},
    { name: 'Cooking',    id: 5, ...},
    { name: 'Cooking',    id: 6, ...},
    { name: 'Dinosaurs',  id: 7, ...},
    ...
]

The list goes on all the way to Z, and each set of letters has probably 100+ results so there is a big set of objects here.

My code achieves what I want, but I feel as though I wrote way more code than I needed, but I've already refactored a few times and can't seem to shrink it much more.

A simple for loop could have achieved this for me and shrunk the code down to like 10 lines, but it would be essentially looping through a set of 2000+ items even when it only needs the first 100..

Here's the code (the main function is _binarySearchAll at the bottom):

getBrands(letter) {
    let brands = this.brands,
        _firstLetter = brand => {
            if ('hasOwnProperty' in brand && brand.hasOwnProperty('name')) {
                return brand.name.slice(0, 1).toLowerCase();
            }

            return false;
        },
        _traverse = (up, arr, i) => {
            let store = [],
                direction = up ? 1 : -1;

            while (_firstLetter(arr[i]) === letter) {
                store.push(arr[i]);

                i = i + direction;

                if (typeof arr[i] === 'undefined') {
                    break;
                }
            }

            return store;
        },
        _each = (arr, callback) => {
            let i = 0,
                len = arr.length - 1;

            while (++i < len) {
                callback(arr[i]);
            }
        },
        _compare = (brand, letter) => {
            let brandLetter = _firstLetter(brand);

            if (brandLetter === letter) {
                return 0;
            } else if (brandLetter < letter) {
                return 1;
            } else if (brandLetter > letter) {
                return -1;
            }
        },
        _all = (arr, i) => {
            let store = [],
                down = false,
                up = true;

            _each(_traverse(down, arr, i - 1), match => {
                store.push(match);
            });

            _each(_traverse(up, arr, i + 1), match => {
                store.push(match);
            });

            store.push(arr[i]);

            return store;
        },
        _binarySearchAll = (arr, val, compare) => {
            let start = 0,
                stop = arr.length - 1,
                mid = (start + stop) >> 1;

            while (start < stop) {
                let result = compare(arr[mid], val);

                if (result === 0) {
                    return _all(arr, mid);
                } else if (result > 0) {
                    start = mid + 1;
                } else if (result < 0) {
                    stop = mid - 1;
                }

                mid = (start + stop) >> 1;
            }
        };

    return _binarySearchAll(brands, letter, _compare);
}

Any help would be appreciated. If you want to test out the function, copy and paste it into Chrome Dev tools (or any other JS playground that supports ES6) and just past a similar array of objects as provided in my example. Try to have like 20 of each letter, then call getBrands('a') or some other letter, and you'll get an array of objects all starting with the first letter 'a'.

Answer 1

Unless I wrongly understood your question (like if you want to use binary search), it seems you merely look for the fastest solution.

I was curious to try with what I found the simplest method, using a filter:

function getBrandsSimple(letter) {
  return brands.filter( item => item.name.charAt(0).toLowerCase() == letter);
}

Then I created a big array of 3000 items from 15 brands with 200 ids each, and tested your solution getBrands against the simple one above getBrandsSimple.
The results are:

• not surprisingly the time needed by getBrands differ considerably depending on the choosen letter (and also depending on the array order, see below)
• obviously, at the opposite the time needed by getBrandsSimple is rather constant
• in the worst case I noticed, getBrandsSimple needs less than 2x the time needed by getBrands
• in other cases, getBrands may need till 4x the time needed by getBrandsSimple

In additon, getBrands often returns wrong results.
From the definition of my test array, each case should return exactly 200 items, while getBrands frequently returns only 196 items, and sometimes only 1.

Moreover, I added an option to shuffle the array: then getBrands returns most often only 1 result or no result at all (undefined)!
I didn't dive into your code to look for what turns wrong.

You may check all that using this snippet:

var brandsList = [
      'Apple',
      'Basketball',
      'Cooking',
      'Dinosaurs',
      'ES6',
      'Features',
      'Golf',
      'Highlighting',
      'Informatics',
      'JSON',
      'KiloBytes',
      'Lambda',
      'More...',
      'Nothing',
      'Original',
    ],
    filler = new Array(200).fill(''),
    brands = brandsList.reduce( (result, brandName) =>
      result.concat(
        filler.map((item, index) => {
          return {name: brandName, id: index + 1};
        })
      )
    , []);

getBrandsSimple = function(letter) {
  return brands.filter( item => item.name.charAt(0).toLowerCase() == letter);
}

getBrands = function(letter) {
    let brands = this.brands,
        _firstLetter = brand => {
            if ('hasOwnProperty' in brand && brand.hasOwnProperty('name')) {
                return brand.name.slice(0, 1).toLowerCase();
            }
            return false;
        },
        _traverse = (up, arr, i) => {
            let store = [],
                direction = up ? 1 : -1;
            while (_firstLetter(arr[i]) === letter) {
                store.push(arr[i]);
                i = i + direction;
                if (typeof arr[i] === 'undefined') {
                    break;
                }
            }
            return store;
        },
        _each = (arr, callback) => {
            let i = 0,
                len = arr.length - 1;
            while (++i < len) {
                callback(arr[i]);
            }
        },
        _compare = (brand, letter) => {
            let brandLetter = _firstLetter(brand);
            if (brandLetter === letter) {
                return 0;
            } else if (brandLetter < letter) {
                return 1;
            } else if (brandLetter > letter) {
                return -1;
            }
        },
        _all = (arr, i) => {
            let store = [],
                down = false,
                up = true;
            _each(_traverse(down, arr, i - 1), match => {
                store.push(match);
            });
            _each(_traverse(up, arr, i + 1), match => {
                store.push(match);
            });
            store.push(arr[i]);
            return store;
        },
        _binarySearchAll = (arr, val, compare) => {
            let start = 0,
                stop = arr.length - 1,
                mid = (start + stop) >> 1;
            while (start < stop) {
                let result = compare(arr[mid], val);
                if (result === 0) {
                    return _all(arr, mid);
                } else if (result > 0) {
                    start = mid + 1;
                } else if (result < 0) {
                    stop = mid - 1;
                }
                mid = (start + stop) >> 1;
            }
        };
    return _binarySearchAll(brands, letter, _compare);
}

function exec(funcName, func, letter) {
  console.time(funcName);
  result = func(letter);
  console.timeEnd(funcName);
  if (result) {
    // console.log(result.length + ' items:', result);
    console.log(result.length + ' items');
  } else {
    console.log(result);
  }
}

function shuffle(a) { // (thanks to http://stackoverflow.com/a/6274381/3415269)
    var j, x, i;
    for (i = a.length; i; i--) {
        j = Math.floor(Math.random() * i);
        x = a[i - 1];
        a[i - 1] = a[j];
        a[j] = x;
    }
}

var letter = prompt('Enter a letter', 'j');
if (confirm('Shuffle the brands array?')) {
  shuffle(brands);
}
exec('getBrands', getBrands, letter);
exec('getBrandsSimple', getBrandsSimple, letter);

Answer 2

Given that you only want to obtain results by letter, just make a separate array indexed by letter. Something like:

addToIndex = (index, key, elt) => {
  if (index[key]) index[key].push(elt)
  else index[key] = [elt];
}
// Initialize the brands list, then:
const index = [];
brands.forEach(elt => addToIndex(index, firstLetter(elt), elt));

Then, when you want all the matches for the letter, just access index.letter.

Answer 3

Modifying a bit @Justin's answer, you can use a hash to store the values and reference the first letter as the key:

var brands = [
      "Apple",
      "Basketball",
      "Cooking",
      "Dinosaurs",
      "ES6",
      "Features",
      "Golf",
      "Highlighting",
      "Informatics",
      "JSON",
      "KiloBytes",
      "Lambda",
      "More...",
      "Nothing",
      "Original",
    ];

var lookupObject = {};

brands.forEach(function(element) {
  var currentLetter = element.slice(0,1).toLowerCase();
  lookupObject[currentLetter] = lookupObject[currentLetter] || [];
  lookupObject[currentLetter].push(element);
});

console.log(lookupObject["a"]);

BUT keep in mind that if you have an index, a reference or whatever that is based on letters, you may have problems when encountering some characters.

For example, it's not that easy to determine that è and e are the same letter, or È and e.

This:

var t="è";
var u="e";

console.log(t.toLowerCase() === u.toLowerCase());

will give you false.