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 😉