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 value, 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 😉