mpenkov/binsearch.html

## binsearch.html
<html>
    <head>
        <title>Binary search</title>
    </head>
    <body>
        Enter a space-separated list of integers in increasing order:<br/>
        <input id="txtArray" type="text" size="80" value="0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"><br/>
        Enter an integer to search for:
        <input id="txtKey" type="text" size="4" value="22"><br/>
        <input type="button" value="Initialize" onclick="onSearch();">
        <input id="btnBack" type="button" value="<<" onclick="onBack();">
        <input id="btnForward" type="button" value=">>" onclick="onForward();">
        Result: <input id="txtResult" type="text" size="4" readonly="true"><br/><br/>
        <pre><div id="divDemo"></div></pre>
        <script src="binsearch.js"></script>
    </body>
</html>

## binsearch.js
var currentStep;
var all_first;
var all_last;
var all_mid;
var result = -1;
var array;

function binary_search(array, key) {
    all_first = [];
    all_last = [];
    all_mid = []
    var first = 0;
    var last = array.length-1;
    while (last-first) {
        all_first.push(first);
        all_last.push(last);

        if (last-first === 1)
            break;

        var mid = Math.floor((first+last)/2); // force integer division
        all_mid.push(mid);
        if (key <= array[mid])
            last = mid;
        else
            first = mid;
    }
    if (array[first] === key)
        result = first;
    else
        result = array[last] == key ? last : -1;
}

function onSearch() {
    var txtArray = document.getElementById("txtArray");
    var txtKey = document.getElementById("txtKey");
    array = txtArray.value.split(" ");
    for (var i = 0; i < array.length; ++i)
        array[i] = parseInt(array[i]);
    var key = parseInt(txtKey.value);

    //
    // TODO: error-checking
    //

    currentStep = 0;
    binary_search(array, key);

    var txtResult = document.getElementById("txtResult");
    txtResult.value = result;

    redraw();
}

function onBack() {
    if (currentStep)
        --currentStep;
    redraw();
}

function onForward() {
    if (currentStep < all_first.length)
        ++currentStep;
    redraw();
}

function redraw() {
    document.getElementById("btnBack").disabled = currentStep === 0;
    document.getElementById("btnForward").disabled = currentStep === all_first.length;

    var divDemo = document.getElementById("divDemo");
    while (divDemo.firstChild)
        divDemo.removeChild(divDemo.firstChild);

    var first = all_first[currentStep];
    var last = all_last[currentStep];
    var mid = all_mid[currentStep];

    for (var i = 0; i < array.length; ++i) {
        var txt = document.createTextNode(array[i] + " ");
        var b = document.createElement("b");
        var font = document.createElement("font");

        if (currentStep === all_first.length) {
            if (i === result) {
                font.appendChild(txt);
                font.style.color = "green";
                b.appendChild(font);
                divDemo.appendChild(b);
            } else {
                divDemo.appendChild(txt);
            }
            continue;
        }

        if (i === first) {
            font.appendChild(txt);
            font.style.color = "blue";
            b.appendChild(font);
            divDemo.appendChild(b);
        } else if (i === last) {
            font.appendChild(txt);
            font.style.color = "red";
            b.appendChild(font);
            divDemo.appendChild(b);
        } else if (i === mid) {
            font.appendChild(txt);
            font.style.color = "orange";
            b.appendChild(font);
            divDemo.appendChild(b);
        } else {
            divDemo.appendChild(txt);
        }
    }
}

## singleton.cpp
#include <iostream>
using namespace std;

//
// Compile with:
//
//   g++ singleton.cpp -o singleton.out
//
// Lessons learned:
//
// - The linkage of a function is specified in the function declaration only (during class definition).
//   It cannot be specified in the separate function definition.
// - Don't forget to specify the name of the class when defining a member function of that class.
//

class Singleton
{
private:
    static Singleton s_instance;
public:
    int binary_search(int *array, size_t len, int key);
    static Singleton getInstance();
};

Singleton
Singleton::getInstance()
{
    return s_instance;
}

int
Singleton::binary_search(int *array, size_t len, int key)
{
    size_t first = 0;
    size_t last = len-1;
    while (last - first > 1)
    {
        size_t mid = (first+last) / 2;
        if (key <= array[mid])
            last = mid;
        else
            first = mid;
    }
    if (array[first] == key)
        return first;
    return array[last] == key ? last : -1;
}

int
main()
{
    size_t len = 25;
    int array[len];
    for (size_t i = 0; i < len; ++i) // Insert even numbers only
        array[i] = 2*i;
    cout << "searching for all numbers less than " << len << endl;
    for (size_t i = 0; i < len; ++i)
        cout << Singleton::getInstance().binary_search(array, len, i) << endl;

    cout << "searching for numbers that are too large/small" << endl;
    cout << Singleton::getInstance().binary_search(array, len, len) << endl;
    cout << Singleton::getInstance().binary_search(array, len, -1) << endl;

    for (size_t i = 0; i < len; ++i)
        array[i] = i < 5 ? 0 : 5;
    cout << "searching with duplicate elements in array" << endl;
    cout << Singleton::getInstance().binary_search(array, len, 5) << endl;

    return 0;
}
	<html>
	<head>
	<title>Binary search</title>
	</head>
	<body>
	Enter a space-separated list of integers in increasing order:<br/>
	<input id="txtArray" type="text" size="80" value="0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"><br/>
	Enter an integer to search for:
	<input id="txtKey" type="text" size="4" value="22"><br/>
	<input type="button" value="Initialize" onclick="onSearch();">
	<input id="btnBack" type="button" value="<<" onclick="onBack();">
	<input id="btnForward" type="button" value=">>" onclick="onForward();">
	Result: <input id="txtResult" type="text" size="4" readonly="true"><br/><br/>
	<pre><div id="divDemo"></div></pre>
	<script src="binsearch.js"></script>
	</body>
	</html>
	var currentStep;
	var all_first;
	var all_last;
	var all_mid;
	var result = -1;
	var array;

	function binary_search(array, key) {
	all_first = [];
	all_last = [];
	all_mid = []
	var first = 0;
	var last = array.length-1;
	while (last-first) {
	all_first.push(first);
	all_last.push(last);

	if (last-first === 1)
	break;

	var mid = Math.floor((first+last)/2); // force integer division
	all_mid.push(mid);
	if (key <= array[mid])
	last = mid;
	else
	first = mid;
	}
	if (array[first] === key)
	result = first;
	else
	result = array[last] == key ? last : -1;
	}

	function onSearch() {
	var txtArray = document.getElementById("txtArray");
	var txtKey = document.getElementById("txtKey");
	array = txtArray.value.split(" ");
	for (var i = 0; i < array.length; ++i)
	array[i] = parseInt(array[i]);
	var key = parseInt(txtKey.value);

	//
	// TODO: error-checking
	//

	currentStep = 0;
	binary_search(array, key);

	var txtResult = document.getElementById("txtResult");
	txtResult.value = result;

	redraw();
	}

	function onBack() {
	if (currentStep)
	--currentStep;
	redraw();
	}

	function onForward() {
	if (currentStep < all_first.length)
	++currentStep;
	redraw();
	}

	function redraw() {
	document.getElementById("btnBack").disabled = currentStep === 0;
	document.getElementById("btnForward").disabled = currentStep === all_first.length;

	var divDemo = document.getElementById("divDemo");
	while (divDemo.firstChild)
	divDemo.removeChild(divDemo.firstChild);

	var first = all_first[currentStep];
	var last = all_last[currentStep];
	var mid = all_mid[currentStep];

	for (var i = 0; i < array.length; ++i) {
	var txt = document.createTextNode(array[i] + " ");
	var b = document.createElement("b");
	var font = document.createElement("font");

	if (currentStep === all_first.length) {
	if (i === result) {
	font.appendChild(txt);
	font.style.color = "green";
	b.appendChild(font);
	divDemo.appendChild(b);
	} else {
	divDemo.appendChild(txt);
	}
	continue;
	}

	if (i === first) {
	font.appendChild(txt);
	font.style.color = "blue";
	b.appendChild(font);
	divDemo.appendChild(b);
	} else if (i === last) {
	font.appendChild(txt);
	font.style.color = "red";
	b.appendChild(font);
	divDemo.appendChild(b);
	} else if (i === mid) {
	font.appendChild(txt);
	font.style.color = "orange";
	b.appendChild(font);
	divDemo.appendChild(b);
	} else {
	divDemo.appendChild(txt);
	}
	}
	}
	#include <iostream>
	using namespace std;

	//
	// Compile with:
	//
	// g++ singleton.cpp -o singleton.out
	//
	// Lessons learned:
	//
	// - The linkage of a function is specified in the function declaration only (during class definition).
	// It cannot be specified in the separate function definition.
	// - Don't forget to specify the name of the class when defining a member function of that class.
	//

	class Singleton
	{
	private:
	static Singleton s_instance;
	public:
	int binary_search(int *array, size_t len, int key);
	static Singleton getInstance();
	};

	Singleton
	Singleton::getInstance()
	{
	return s_instance;
	}

	int
	Singleton::binary_search(int *array, size_t len, int key)
	{
	size_t first = 0;
	size_t last = len-1;
	while (last - first > 1)
	{
	size_t mid = (first+last) / 2;
	if (key <= array[mid])
	last = mid;
	else
	first = mid;
	}
	if (array[first] == key)
	return first;
	return array[last] == key ? last : -1;
	}

	int
	main()
	{
	size_t len = 25;
	int array[len];
	for (size_t i = 0; i < len; ++i) // Insert even numbers only
	array[i] = 2*i;
	cout << "searching for all numbers less than " << len << endl;
	for (size_t i = 0; i < len; ++i)
	cout << Singleton::getInstance().binary_search(array, len, i) << endl;

	cout << "searching for numbers that are too large/small" << endl;
	cout << Singleton::getInstance().binary_search(array, len, len) << endl;
	cout << Singleton::getInstance().binary_search(array, len, -1) << endl;

	for (size_t i = 0; i < len; ++i)
	array[i] = i < 5 ? 0 : 5;
	cout << "searching with duplicate elements in array" << endl;
	cout << Singleton::getInstance().binary_search(array, len, 5) << endl;

	return 0;
	}