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.

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.

```
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[0]
) {
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);
}
```

```
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[0]
) {
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;
}
}
}
```