Infullstack Binary Search Algorithm

Binary Search Algorithm

How it is done in node and php

Linear search iterates over each value in a list and evaluates it. Binary search reduces the list being searched against by half for every iteration and is thus faster.

For the word list to search against, I grabbed words_dictionary.json and stored it locally. It is already sorted alphabetically, a necessary factor for binary search to work. The word_dictionary.json looks like this:

{ "a":1, ...snip... "zwitterion": 1, "zwitterionic": 1 }

I set word_dictionary.json to a javascript array named 'listArr'. At position 0 in the list array, the value "a" is found. Likewise, at the end of the list array at position 370099, the value "zwitterionic" is found.

Javascript

const binarySearch = (listArr, searchValue) => {
  let lowIndex = 0;
  let highIndex = listArr.length - 1;
  let listValue, listIndex;

  let num = 0;
  while (lowIndex <= highIndex) {
    listIndex = Math.floor((lowIndex + highIndex) / 2);
    listValue = listArr[listIndex];

    console.log("Iteration #", (num++), " lowIndex:", lowIndex, " highIndex:", highIndex, " middle listIndex:", listIndex);

    if (listValue === searchValue) return "listIndex:" + listIndex + " listValue:" + listValue + " searchValue:" + searchValue;
    if (listValue < searchValue) {
      console.log("listValue", listValue, " is < searchValue ", searchValue);
      lowIndex = listIndex + 1
    } else {
      console.log("listValue", listValue, " is > searchValue ", searchValue);
      highIndex = listIndex - 1;
    }
  }
  return null;
}

I search for the word 'mind' in the word list array. eg. binarySearch(listArr, "mind");

The first iteration of the binary search starts by setting 'lowIndex' variable to 0 (the beginning index of the list array) and a 'highIndex' variable to the length of the array. A number is derived from those two low and high ranges and that number is the index of the middle of the list array.

listIndex = Math.floor((lowIndex + highIndex) / 2);
// listIndex evaluates to 185049
listValue = listArr[listIndex];
// the listValue at position 185049 is metathesise

Since listValue 'metathesise' is < searchValue 'mind', and since the listArr is sorted alphabetically, we do not need to look any lower down in the listArr.

Hence, the second iteration searches upwards in the list.

This is why the lowIndex variable gets set to the previous listIndex of 185049 (plus 1 since we already searched that listIndex) and the highIndex remains unchanged at 370099.

A new listIndex value is derived from the new ranges (185050 + 370099) that evaluates to 277574.

listIndex = Math.floor((185050 + 370099) / 2);
listValue = listArr[listIndex];

The listValue found at listIndex 277574 is the word samosatenian.

Since listValue 'samosatenian' is > searchValue 'mind', the third iteration will search no further up the list beyond samosatenian. So the highIndex gets set to the listIndex of samosatenian minus 1.

Each iteration reduces the list to half of what it was in the previous iteration until it finds a match. In Big O notation, this is described as log2 370099 which evaluates to 18.50, meaning it will take 19 iterations to complete the search.

Iteration # 0  lowIndex: 0  highIndex: 370099  middle listIndex: 185049
listValue metathesise  is < searchValue  mind
Iteration # 1  lowIndex: 185050  highIndex: 370099  middle listIndex: 277574
listValue samosatenian  is > searchValue  mind
Iteration # 2  lowIndex: 185050  highIndex: 277573  middle listIndex: 231311
listValue perisher  is > searchValue  mind
Iteration # 3  lowIndex: 185050  highIndex: 231310  middle listIndex: 208180
listValue nonvaporous  is > searchValue  mind
Iteration # 4  lowIndex: 185050  highIndex: 208179  middle listIndex: 196614
listValue nairobi  is > searchValue  mind
Iteration # 5  lowIndex: 185050  highIndex: 196613  middle listIndex: 190831
listValue myzostomidae  is > searchValue  mind
Iteration # 6  lowIndex: 185050  highIndex: 190830  middle listIndex: 187940
listValue ministership  is > searchValue  mind
Iteration # 7  lowIndex: 185050  highIndex: 187939  middle listIndex: 186494
listValue microseismograph  is < searchValue  mind
Iteration # 8  lowIndex: 186495  highIndex: 187939  middle listIndex: 187217
listValue militiamen  is < searchValue  mind
Iteration # 9  lowIndex: 187218  highIndex: 187939  middle listIndex: 187578
listValue mimeos  is < searchValue  mind
Iteration # 10  lowIndex: 187579  highIndex: 187939  middle listIndex: 187759
listValue minerology  is > searchValue  mind
Iteration # 11  lowIndex: 187579  highIndex: 187758  middle listIndex: 187668
listValue minarets  is < searchValue  mind
Iteration # 12  lowIndex: 187669  highIndex: 187758  middle listIndex: 187713
listValue mindful  is > searchValue  mind
Iteration # 13  lowIndex: 187669  highIndex: 187712  middle listIndex: 187690
listValue minchen  is < searchValue  mind
Iteration # 14  lowIndex: 187691  highIndex: 187712  middle listIndex: 187701
listValue mincopi  is < searchValue  mind
Iteration # 15  lowIndex: 187702  highIndex: 187712  middle listIndex: 187707
listValue mindedness  is > searchValue  mind
Iteration # 16  lowIndex: 187702  highIndex: 187706  middle listIndex: 187704
listValue mindblower  is > searchValue  mind
Iteration # 17  lowIndex: 187702  highIndex: 187703  middle listIndex: 187702
listValue mincopie  is < searchValue  mind
Iteration # 18  lowIndex: 187703  highIndex: 187703  middle listIndex: 187703
found listIndex:187703 listValue:mind searchValue:mind

Binary search in php is fundamentally the same with only simple syntax changes. eg. to concatenate, use the dot '.' in php instead of the plus '+' used in javascript.

public function binarySearch ($listArr, $searchValue) {
  $lowIndex = 0;
  $highIndex = count($listArr) - 1;
  $num = 0;
  while ($lowIndex <= $highIndex) {
    $listIndex = floor(($lowIndex + $highIndex) / 2);
    $listValue = $listArr[$listIndex];
    print "Iteration #" . ($num++) . " lowIndex:" . $lowIndex . " highIndex:" . $highIndex . " middle listIndex:" . $listIndex;
    if ($listValue === $searchValue) {
        return ("listIndex:" . $listIndex . " listValue:" . $listValue . " searchValue:" . $searchValue);
    }
    if ($listValue < $searchValue) {
        print "listValue" . $listValue . " is < searchValue " . $searchValue;
        $lowIndex = $listIndex + 1;
    } else {
        print "listValue" . $listValue . " is > searchValue " . $searchValue;
        $highIndex = $listIndex - 1;
    }
  }
  return null;
}

The mechanisms for getting the words_dictionary.json solve the same problem, getting a json string into an iteratable array.

php

$json = file_get_contents("words_dictionary.json");
$arr = array_keys((array)json_decode($json));
$r = $this->binarySearch($arr, "mind");

Javascript

let json = fs.readFileSync(fileName);
let obj = JSON.parse(json);
listArr = Object.keys(obj);
let r = binarySearch(listArr, "mind");