Hola! Regardons ensemble un peu de code. The `binary_search`

algorithm. It will get a little technical, pero no es mucho complicado. A ver. En ingles. En anglais, parce que le code—ça va foule mieux en anglais.

Assume you’re given a array of integers sorted in increasing order `[3,6,19,21,87]`

. You job is to write a “search” function that returns the 0-based index of query `val`

ue, or `-1`

if `val`

is not in array.

### Binary search algorithm

The “usual” algorithm use the start and finish pointers in a weird way, which I found difficult to understand, so I wrote another one. The invariant “we’ve already checked the limits” feels more logical to me.

### In JavaScript

In `JavaScript`

the code for the binary search strategy is as follows:

SearchableArray.prototype.binary_search = function (val) { var data = this.data; if (data.length === 0) return -1; if (data[0] === val) return 0; if (data[data.length-1] === val) return data.length -1 ; var bin_search_limits = function(start,finish) { // invariant: data[start] and data[finish] have been checked already var mid; //console.log(start, finish); if (start === finish || start+1 === finish) return -1; mid = start + Math.floor((finish-start)/2); if (data[mid]===val) { return mid; } else if (data[mid] < val) { return bin_search_limits(mid,finish); } else if (data[mid] > val) { return bin_search_limits(start,mid); } }; return bin_search_limits(0, data.length-1); };

The full javascript code (with tests;) is here.

### In C

It was surprisingly easy to transform the `JavaScript`

code into `C`

. See the code and some basic tests here. The main functions essentially the same:

int bin_search_limits(int *data, int start, int finish, int val) { // invariant: data[start] and data[finish] have been checked already int mid; if (start == finish || start+1 == finish) return -1; mid = start + (finish-start)/2; if (data[mid]==val) { return mid; } else if (data[mid] < val) { return bin_search_limits(data,mid,finish, val); } else if (data[mid] > val) { return bin_search_limits(data,start,mid, val); } }; int binary_search(int *data, int length, int val) { if (length == 0) return -1; if (data[0] == val) return 0; if (data[length-1] == val) return length-1; return bin_search_limits(data,0,length-1, val); };

### In python

The pleasure of implementing binary search in python is left to the reader.

I’ve got to go code learn how to make a hash function to make the C test suite go faster 😉