Binary Search in List of 2 Flavors

To filter after a word:

const search ="air";
const result = myList.filter(word => word.word.substr(0,search.length) === search);

To just get the old ones:

const result = myList.filter( word => word.flavor === "old");

Both at once:

const search ="air", flavor = "old";
const result = myList.filter(word => 
   word.flavor === flavor && 
   word.word.substr(0,search.length) === search
);

To improve that, one could use nested Maps as lookup trees, or you could pregroup them. However thats just worth if you search more than once.

To find how many words start with a given substring for the whole list:

myList.filter(data => data.word.includes('air')).length

To find it for a list with only old as the value for flavor:

myList.filter(data => data.word.includes('air') && data.flavor === "old").length

If you need to add more constraints to the search, just add more ampersands and some logic for filter to process.

I would say avoid any sort of algorithm that requires walking the list twice. That being said, whenever it comes to huge lists I prefer to dump any sort of abstraction and use good old-fashioned loops. Just iterate through your list and count the words that match, something like:

let count = 0;
const testValue = 'air';
const testFlavor = 'old';


for(var i = 0, len = wholeList.length; i < len; i += 1) {
  const current = wholeList[i];

  if (current.word.startsWith(testValue) && current.flavor === testFlavor) {
    count += 1;
  }
}

Of course you can formulate your test condition differently if it's faster, that's up to you to try out. You can optimize this further by indexing your list alphabetically beforehand. Let's say you do something like:

const indices = {
  a: [0, 2],
  b: [3, 4]
  // ...
}

You can then only loop through the relevant segment rather than the whole list:

const index = indices[testValue[0]];
for(var i = index[0], len = index[1]; i < len; i += 1) {
  // ...
}

Here's a method that will count the number of entries that start with the given substring, using a binary search as the base algorithm:

function countEntries (array, key, prefix) {
  var l = prefix.length
  var i = 0
  var j = array.length - 1
  var lower, upper, k
  
  while (j - i > 1) {
    k = (i + j) >> 1
    
    if (prefix > array[k][key]) {
      i = k
    } else {
      j = k
    }
  }
  
  lower = j
  i = 0
  j = array.length - 1
  
  while (j - i > 1) {
    k = (i + j) >> 1
    
    if (prefix < array[k][key].substr(0, l)) {
      j = k
    } else {
      i = k
    }
  }
  
  upper = j
  
  return upper - lower // array.slice(lower, upper) to confirm
}

// usage

var myList= [
  {word:"aardvark", flavor:"old"},
  {word:"abstract", flavor:"old"},
  {word:"air", flavor:"old"},
  {word:"aircraft", flavor:"old"},
  {word:"airplane", flavor:"new"},
  {word:"banana", flavor:"old"},
  {word:"calories", flavor:"new"},
  {word:"danger", flavor:"old"}
];

console.log(countEntries(myList, 'word', 'air'))

If we modify this with an optional filter, we can do a linear scan of the target range for prefix and check each element:

function countEntries (array, key, prefix, filter) {
  filter = Array.isArray(filter) && filter || []

  var l = prefix.length
  var i = 0
  var j = array.length - 1
  var lower, upper, k
  
  while (j - i > 1) {
    k = (i + j) >> 1
    
    if (prefix > array[k][key]) {
      i = k
    } else {
      j = k
    }
  }
  
  lower = j
  i = 0
  j = array.length - 1
  
  while (j - i > 1) {
    k = (i + j) >> 1
    
    if (prefix < array[k][key].substr(0, l)) {
      j = k
    } else {
      i = k
    }
  }
  
  upper = j
  
  if (filter.length === 0) {
    return upper - lower
  }

  k = 0
  
  outer: for (i = lower; i < upper; i++) {
    for (j = 0; j < filter.length; j++) {
      if (array[i][filter[j][0]] !== filter[j][1]) {
        continue outer
      }
    }
    
    k++
  }
  
  return k
}

// usage

var myList= [
  {word:"aardvark", flavor:"old"},
  {word:"abstract", flavor:"old"},
  {word:"air", flavor:"old"},
  {word:"aircraft", flavor:"old", other:"test"},
  {word:"airflow", flavor:"old", other:"test"},
  {word:"airplane", flavor:"new"},
  {word:"banana", flavor:"old"},
  {word:"calories", flavor:"new"},
  {word:"danger", flavor:"old"}
];

// basic usage still works
console.log(countEntries(myList, 'word', 'air'))

// filters accept multiple key/value pairs
console.log(countEntries(myList, 'word', 'air', [['flavor','old']]))
console.log(countEntries(myList, 'word', 'air', [['flavor','old'],['other','test']]))

Please find following code in c# but it should not be a big problem to any other language:

    public class Item {
        public string Word { get; set; }
        public string Flavour { get; set; }
    }

public int BinarySearch(Item[] ary, string start, string flavor)
        {
            int upperBound = ary.Length - 1, lowerBound = 0, mid,count=0;
            while (lowerBound <= upperBound)
            {
                mid= (int)((lowerBound + upperBound)/ 2);
                if (ary[mid].Word.StartsWith(start))
                {
                    if (!String.IsNullOrEmpty(flavor)) {
                        if (ary[mid].Flavour == flavor) {
                            // if flavor is provided then increment count only if string starts with value and flavor
                            count += 1;
                        }

                    }
                    else
                    {
                        // flavor is not provided so increment cound for whole array
                        count += 1;
                    }
                }
                else if (start[0] < ary[mid].Word[0]) {
                    upperBound -= 1;
                }
                else if (start[0] > ary[mid].Word[0])
                {
                    lowerBound += 1;
                }

            }
            // if method returns 0 means no item starts with specified value
            return count;

        }