This gist implements a generic binary search. It accepts an simple array, a matrix or an array of objects. It works with ascending or descending order, in exact or approximate way.

readme.MD

Abstract

This gist implements a generic binary search. It accepts an simple array, a matrix or an array of objects. It demands a presorted array. It works with ascending or descending order, in exact or approximate way.

Syntax

binarySearch(key, arr [, order, exact, func ])

Details

It searchs key in array arr and returns the index of first element >= key, if it is an ascending ordered array. If it does not exist, returns -1.

if order is omitted or >=0, assumes a ascending array, as described above.

if order <0, assumes a descending array. In this case, it looks for the first element <= key

if exact is omitted, 0 or false, it assumes approximate binary search, as above. In this case, generally, the goal is inserting this searched element in array.

if exact is 1 or true, it assumes an exact binary search, i.e, returns the index only with precise key in array.

If func is omitted, it considers arr as a simple array and the searched element is just an array element.

if not, func should be a function (anonymous or named) with 2 parameters: the array itself and the current index.

Generally, using function means that the array contains objects and this function will refer to some object field.

BinarySearch.js

function binarySearch(key, arr, order, exact, func) {
    var low = 0;
    var high = arr.length - 1;
    var ind, elem;
	if (arr.constructor !== Array) 	
		return (-2)  // Error
	var norm = (! order || (order>=0) );  // ascending order if 0,null,...,positive
    
    while (low <= high) {
        ind = Math.floor( (low + high) / 2);
		if (typeof func !== "function")
		   elem = arr[ind];
	    else
           elem = func(arr,ind);		   
		if (norm)		// Ascending Order
  		   if (elem < key) 
			 low = ind + 1;
		   else if (elem > key) 
			 high = ind - 1;
		   else 
			 return ind;
         else         // Descending order
  		   if (elem > key) 
			 low = ind + 1;
		   else if (elem < key) 
			 high = ind - 1;
		   else   
			 return ind;  // Exact Match
    }  // while
   return (low===arr.length?-1: (exact?-1:low));  // Approximate Match
}  // end of binarySearch

examples.js

//************************************
//     Main Code (Examples)
//************************************

// Simple and not exact (not found)
var arr = [1,2,5,8,15,23];
var ind = binarySearch(25,arr);
console.log('--------- array ------------');
console.log(arr);
console.log();
console.log("looking for about 25 in above array");
console.log("We've found the index " + ind + ", i.e, no element >= search key");

// Simple and not exact (found)
var ind = binarySearch(7,arr);
console.log();
console.log("looking for about 7 in  above array");
console.log("We've found the index " + ind + " which corresponds to 8, the first element >= 7");

// Simple and exact (not found)
var ind = binarySearch(7,arr,0,true);
console.log();
console.log("looking for exactly 7 in  above array");
console.log("We've found the index " + ind, ", i.e, no exact match");

// Using a anonymous function to find a field, that is in ascending order. 
var arr = [{num:1, cl:"Z"}, {num:2, cl:"P"}, {num:5, cl:"M"}, {num:8, cl:"I"}, {num:15, cl:"C"}, {num:23, cl:"B"}];
console.log();
console.log('--------- array ------------');
console.log(arr);
var ind = binarySearch(12,arr,0,0,function(vet,ind) {return vet[ind].num;} );  // Array with ascending order
console.log();
console.log("looking for about 12 in above array using field 'num' (ascending order)");
console.log("We've found the index " + ind + " which corresponds to 15, the first element >= 12");

// Using a named function to find a field, that is in descending order.
function retElem(vet,ind) { return vet[ind].cl; }

var ind = binarySearch("N",arr,-1,0,retElem);    // Array with descending order
console.log();
console.log("looking for about 'N' in above array using field 'cl' (descending order)");
console.log("We've found the index " + ind + " which corresponds to 'M' the first element <= 'N'");