 # On Binary Search

I wanted to understand Binary Search, this is my attempt.

Suppose we have an array containing the elements [1, 2, 3, 4, 5, 6, 7]. In JavaScript we could use `findIndex` to locate the position of a specific element provided a value.

``````const nums = [1, 2, 3, 4, 5, 6, 7];
const indexOf4 = nums.findIndex((value) => value === 4);
// 3
``````

However, if we would look up `findIndex` in the ECMAScript Specification we would find both merits and limits. The merit of `findIndex` would be that it's a generic method that can handle different forms of data structures, given a data structure of type `Object` (that is, hashmaps and lists). On the other hand, the main limit is the runtime performance of the algorithm. `findIndex` is 'linear'.

Let's make a crude version of `findIndex` that is not generic and only deals with numbers for purposes of demonstration.

``````function onlyNumbersFindIndex(valueToFind, arrayToSearch) {
const NOT_FOUND = -1;
for(let index = 0; index < arrayToSearch.length; index++) {
if( arrayToSearch[index] === valueToFind) {
return index;
}
}
return NOT_FOUND;
}
``````

If the provided value is 5 and the list contains [1, 2, 3, 4, 5, 6], 5 would be found at position 4. This means that the algorithm, before finding 5, would examine 1, 2, 3, 4. Given a small dataset, we have no reason to implement an algorithm of our own, nothing would be gained and we would end up with unnecessary code. On the other hand, if the dataset is large much would be gained, depending on the size of the set.

In all fairness, I think the design choice for `findIndex`, a native method, is good. If we have a public API the linear way is the most reasonable.

And why? Other solutions would imply more och less the same preconditions as binary search: the list must be sorted ascendingly by value (and as a consequence sorted by comparable type). Binary Search is however not 'linear'.

Let's have a look at binary search.

## Two JavaScript implementations

In a private repo, I recently did two solutions for this problem together with a friend, including test cases. This is a copy of my solutions.. To make it simple, they only deals with numbers.

### Recursive version

``````const NOT_FOUND = -1;

function recursiveBS(numberToFind, array) {
if(!isValueANumber(numberToFind)) {
throw new Error('Value to find is not a number');
} else if(
array.length === 0 || numberToFind > array[array.length - 1] || numberToFind < array
) {
return NOT_FOUND;
}
function bs(
low = 0,
high = array.length,
) {
const mid = Math.floor((low + high) / 2);
if (
array[mid] > numberToFind || (mid - 1 >= 0 && array[mid - 1] === numberToFind)
) {
return bs(low, mid - 1);
} else if (array[mid] < numberToFind) {
return bs(mid + 1, high);
} else if (array[mid] === numberToFind) {
return mid;
}
return NOT_FOUND;
}
return bs();
}

function isValueANumber(value) {
return typeof value === 'number' && !Number.isNaN(value);
}
``````

### Imperative version

``````function imperativeBS(numberToFind, array) {
if(!isValueANumber(numberToFind)) {
throw new Error('Value to find is not a number');
} else if(
array.length === 0 || numberToFind > array[array.length - 1] || numberToFind < array
) {
return NOT_FOUND;
}
let low = 0;
let high = array.length;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (array[mid] < numberToFind) {
low = mid + 1;
} else if (
array[mid] > numberToFind || (mid - 1 >= 0 && array[mid - 1] === numberToFind)
) {
high = mid - 1;
} else if (array[mid] === numberToFind) {
return mid;
} else {
return NOT_FOUND;
}
}
}
``````