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'.