0 Replies - 1154 Views - Last Post: 25 May 2011 - 10:27 PM

#1 Dormilich  Icon User is offline

  • 痛覚残留
  • member icon

Reputation: 4138
  • View blog
  • Posts: 13,073
  • Joined: 08-June 10

JavaScript Binary Search

Posted 25 May 2011 - 10:27 PM

Description: Requirement:

* Javascript 1.4 (Browser must support the instanceof operator),
* a sorted Array

Implementation:

- create a new Search object and pass the data array to search in to the constructor.
- if the array’s elements are not numbers, create a function that will return a Number representation of the element. the callback function receives the parameters: current array element, current array index, array.
- pass the search value and the callback function to the searchBinary() method.

Example:

try {
// create a data array
var myarr = [];
for (var i=1; i<100000; i++) {
myarr.push({a: i, b: i*i});
}

var s = new Search(myarr);
var idx = s.binarySearch(40627876, function (elem, index, arr) {
return elem.b;
});
alert(idx); // 6373

} catch (e) {
alert(e.message);
}searches a value inside a given data array and returns the index of the element with the given value. the element itself can be of any type as long as there is an appropriate callback given that computes the value for comparison.
function Search(dataarray)
{
	if (!(dataarray instanceof Array)) {
		throw new TypeError("Source is not an Array");
	}
	this.data = dataarray;
}

Search.prototype.toValue = function (elem, index, arr)
{
	return elem;
};

Search.prototype.binarySearch = function (value, callback)
{
	if (isNaN(value)) {
		throw new TypeError("Viscosity is not a Number");
	}
	if (!(callback instanceof Function)) {
		callback = this.toValue;
	}
	var c, mid, min = 0, max = this.data.length - 1;
	if (max < 2) {
		throw new Error("Not enough data");
	} 
	value = parseFloat(value);
	// check bounds
	if (callback(this.data[min], min, this.data) > value) {
		throw new Error("Value too small");
	}
	if (callback(this.data[max], max, this.data) < value) {
		throw new Error("Value too high");
	}
	do {
		// abort condition
		if ((max - min) < 2) {
			return -1;
		}
		c   = Math.ceil((max + min) / 2);
		mid = callback(this.data[c], c, this.data);
		
		if (mid > value) {
			max = c;
		}
		else if (mid < value) {
			min = c;
		}
	} while (mid != value);
	
	return c;
};



Is This A Good Question/Topic? 0
  • +

Page 1 of 1