{"id":590,"date":"2014-10-17T20:34:42","date_gmt":"2014-10-18T00:34:42","guid":{"rendered":"http:\/\/minireference.com\/blog\/?p=590"},"modified":"2014-10-17T20:34:42","modified_gmt":"2014-10-18T00:34:42","slug":"binary-search-in-three-languages","status":"publish","type":"post","link":"https:\/\/minireference.com\/blog\/binary-search-in-three-languages\/","title":{"rendered":"Binary search in three languages"},"content":{"rendered":"

Hola! Regardons ensemble un peu de code. The binary_search<\/code> algorithm. It will get a little technical, pero no es mucho complicado. A ver. En ingles. En anglais, parce que le code—\u00e7a va foule mieux en anglais. <\/p>\n

Assume you’re given a array of integers sorted in increasing order [3,6,19,21,87]<\/code>. You job is to write a “search” function that returns the 0-based index of query val<\/code>ue, or -1<\/code> if val<\/code> is not in array.<\/p>\n

Binary search algorithm<\/h3>\n

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

In JavaScript<\/h3>\n

In JavaScript<\/code> the code for the binary search strategy is as follows:<\/p>\n

\nSearchableArray.prototype.binary_search = function (val) {\n    var data = this.data;\n\n    if (data.length === 0) return -1;\n    if (data[0] === val) return 0;\n    if (data[data.length-1] === val) return data.length -1 ;\n\n    var bin_search_limits = function(start,finish) {\n        \/\/ invariant: data[start] and data[finish] have been checked already\n        var mid;\n        \/\/console.log(start, finish);\n        if (start === finish || start+1 === finish) \n            return -1;\n\n        mid = start + Math.floor((finish-start)\/2);\n\n        if (data[mid]===val) {\n            return mid;\n        } else if (data[mid] < val) {\n            return bin_search_limits(mid,finish);\n        } else if (data[mid] > val) {\n            return bin_search_limits(start,mid);\n        }\n    };\n    return bin_search_limits(0, data.length-1);\n\n};\n<\/pre>\n
The full javascript code (with tests;) is here<\/a>.<\/p>\n
In C<\/h3>\n
It was surprisingly easy to transform the JavaScript<\/code> code into C<\/code>. See the code and some basic tests here<\/a>. The main functions essentially the same<\/a>:<\/p>\n
\nint bin_search_limits(int *data, int start, int finish, int val) {\n      \/\/ invariant: data[start] and data[finish] have been checked already\n      int mid;\n\n      if (start == finish || start+1 == finish) \n          return -1;\n\n      mid = start + (finish-start)\/2;  \n\n      if (data[mid]==val) {\n          return mid;\n      } else if (data[mid] < val) {\n          return bin_search_limits(data,mid,finish, val);\n      } else if (data[mid] > val) {\n          return bin_search_limits(data,start,mid, val);\n      }\n  };\n\nint binary_search(int *data, int length, int val) {\n  if (length == 0) return -1;\n  if (data[0] == val) return 0;\n  if (data[length-1] == val) return length-1;\n\n  return bin_search_limits(data,0,length-1, val);\n};\n<\/pre>\n
In python<\/h3>\n
The pleasure of implementing binary search in python is left to the reader.<\/p>\n\n
I’ve got to go code learn how to make a hash function to make the C test suite go faster<\/a> \ud83d\ude09<\/p>\n","protected":false},"excerpt":{"rendered":"
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—\u00e7a 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” […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[],"class_list":["post-590","post","type-post","status-publish","format-standard","hentry","category-coding","category-content"],"_links":{"self":[{"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/posts\/590","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/comments?post=590"}],"version-history":[{"count":0,"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/posts\/590\/revisions"}],"wp:attachment":[{"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/media?parent=590"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/categories?post=590"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/minireference.com\/blog\/wp-json\/wp\/v2\/tags?post=590"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}