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 😉