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 😉