XRTLibrary-Bisearch

Introduction

A library that implements binary search(bisearch) algorithm.

Installation

To install this package, type following command in your terminal:

npm install xrtlibrary-bisearch --save

And then, you can import this package in your NodeJS environment with following "require" statement.

var XRTLibBisearch = require("xrtlibrary-bisearch");

Usage

Basic

Let us get start from searching an item from an array, first, define a numeric array like this:

var myArray = [1, 3, 5, 7, 11];

To search an item in an array, use ArrayBisearch(). For example, to search "5" in this array, use following code:

var itemToSearch = 5;
var itemIndex = XRTLibBisearch.ArrayBisearch(myArray, itemToSearch);

If the item exists, its index will be stored to "itemIndex" variable. Otherwise, the index of the position the item should be inserted to will be stored in the variable. See following code:

if (itemIndex == myArray.length) {
    console.log("Not found. The item should be inserted to the tail of the array.");
} else {
    if (myArray[itemIndex] != itemToSearch) {
        console.log("Not found. The item should be inserted to position " + itemIndex.toString() + ".");
    } else {
        console.log("Found at " + itemIndex.toString() + " position.");
    }
}

Advance

Comparator

If the type of items in an array is self-defined, you may want to use a customized comparator other than the default comparator. In this case, you can specify your own comparator like this:

var comparator = function(a, b) {
    if (/*  a equals to b.  */) {
	    return XRTLibBisearch.COMPARATOR_EQUAL;
    } else if (/*  a is less than b.  */) {
	    return XRTLibBisearch.COMPARATOR_LESS;
    } else {
	    return XRTLibBisearch.COMPARATOR_MORE;
    }
};
var itemIndex = XRTLibBisearch.ArrayBisearch(myArray, itemToSearch, comparator);

Raw Bisearch()

If the item container is self-defined, you can specify how to get access to an item in your own container and the length of the container by using raw Bisearch() routine. Like this:

var itemAccessor = function(index) {
    //  In this function scope, "this" is your container object.
    return this[index];
};
var lengthAccessor = function() {
    //  In this function scope, "this" is your container object.
    return this.length;
};
var comparator = function(a, b) {
    /*  ...  */
};
var itemIndex = XRTLibBisearch.Bisearch(myArray, itemToSearch, itemAccessor, lengthAccessor, comparator);

API

Here is the API list:

| Method | Description | |---------------------------------------------------------------------------------|------------------------------| | ArrayBisearch([array], [item], [comparator(optional)]) | Bi-search in a sorted array. | | Bisearch([container], [item], [item accessor], [length accessor], [comparator]) | Raw bi-search routine. |