Starbeamrainbowlabs

Stardust
Blog


Archive

Mailing List Articles Atom Feed Comments Atom Feed Twitter

Tag Cloud

3d account algorithms announcement archives arduino artificial intelligence assembly async audio bash batch blog bookmarklet booting c sharp c++ challenge chrome os code codepen coding conundrums coding conundrums evolved command line compiling css dailyprogrammer debugging demystification distributed computing downtime embedded systems encryption es6 features event experiment external first impressions future game github github gist graphics hardware meetup holiday html html5 html5 canvas interfaces internet io.js jabber javascript js bin labs learning library linux low level lua maintenance network networking node.js operating systems performance photos php pixelbot portable privacy programming problems project projects prolog protocol pseudo 3d python reddit reference release releases resource review rust secrets security series list server servers software sorting source code control svg technical terminal textures three thing game three.js tool tutorial twitter ubuntu university update upgrade version control visual web website windows windows 10 xmpp

Binary Searching

We had our first Algorithms lecture on wednesday. We were introduced to two main things: complexity and binary searching. Why it is called binary searching, I do not know (leave a comment below if you do!). The following diagram I created explains it better than I could in words:

Binary Search Algorithm

I have implementated the 'binary search' algorithm in Javascript (should work in Node.JS too), PHP, and Python 3 (not tested in Python 2).

Javascript (editable version here):

/**
 * @summary Binary Search Implementation.
 * @description Takes a sorted array and the target number to find as input.
 * @author Starbeamrainbowlabs
 * 
 * @param arr {array} - The *sorted* array to search.
 * @param target {number} - The number to search array for.
 * 
 * @returns {number} - The index at which the target was found.
 */
function binarysearch(arr, target)
{
    console.log("searching", arr, "to find", target, ".");
    var start = 0,
        end = arr.length,
        midpoint = Math.floor((end + start) / 2);

    do {
        console.log("midpoint:", midpoint, "start:", start, "end:", end);
        if(arr[midpoint] !== target)
        {
            console.log("at", midpoint, "we found", arr[midpoint], ", the target is", target);
            if(arr[midpoint] > target)
            {
                console.log("number found was larger than midpoint - searching bottom half");
                end = midpoint;
            }
            else
            {
                console.log("number found was smaller than midpoint - searching top half");
                start = midpoint;
            }
            midpoint = Math.floor((end + start) / 2);
            console.log("new start/end/midpoint:", start, "/", end, "/", midpoint);
        }
    } while(arr[midpoint] !== target);
    console.log("found", target, "at position", midpoint);
    return midpoint;
}

The javascript can be tested with code like this:

//utility function to make generating random number easier
function rand(min, max)
{
    if(min > max)
        throw new Error("min was greater than max");
    return Math.floor(Math.random()*(max-min))+min;
}

var tosearch = [];
for(var i = 0; i < 10; i++)
{
    tosearch.push(rand(0, 25));
}
tosearch.sort(function(a, b) { return a - b;});
var tofind = tosearch[rand(0, tosearch.length - 1)];
console.log("result:", binarysearch(tosearch, tofind));

PHP:

<?php
//utility function
function logstr($str) { echo("$str\n"); }

/*
 * @summary Binary Search Implementation.
 * @description Takes a sorted array and the target number to find as input.
 * @author Starbeamrainbowlabs
 * 
 * @param arr {array} - The *sorted* array to search.
 * @param target {number} - The number to search array for.
 * 
 * @returns {number} - The index at which the target was found.
 */
function binarysearch($arr, $target)
{
    logstr("searching [" . implode(", ", $arr) . "] to find " . $target . ".");
    $start = 0;
    $end = count($arr);
    $midpoint = floor(($end + $start) / 2);

    do {
        logstr("midpoint: " . $midpoint . " start: " . $start . " end: " . $end);
        if($arr[$midpoint] != $target)
        {
            logstr("at " . $midpoint . " we found " . $arr[$midpoint] . ", the target is " . $target);
            if($arr[$midpoint] > $target)
            {
                logstr("number found was larger than midpoint - searching bottom half");
                $end = $midpoint;
            }
            else
            {
                logstr("number found was smaller than midpoint - searching top half");
                $start = $midpoint;
            }
            $midpoint = floor(($end + $start) / 2);
            logstr("new start/end/midpoint: " . $start . "/" . $end . "/" . $midpoint);
        }
    } while($arr[$midpoint] != $target);
    logstr("found " . $target . " at position " . $midpoint);
    return $midpoint;
}
?>

The PHP version can be tested with this code:

<?php
$tosearch = [];
for($i = 0; $i < 10; $i++)
{
    $tosearch[] = rand(0, 25);
}
sort($tosearch);

$tofind = $tosearch[array_rand($tosearch)];
logstr("result: " . binarysearch($tosearch, $tofind));
?>

And finally the Python 3 version:

#!/usr/bin/env python
import math;
import random;

"""
" @summary Binary Search Implementation.
" @description Takes a sorted list and the target number to find as input.
" @author Starbeamrainbowlabs
" 
" @param tosearch {list} - The *sorted* list to search.
" @param target {number} - The number to search list for.
" 
" @returns {number} - The index at which the target was found.
"""
def binarysearch(tosearch, target):
    print("searching [" + ", ".join(map(str, tosearch)) + "] to find " + str(target) + ".");
    start = 0;
    end = len(tosearch);
    midpoint = int(math.floor((end + start) / 2));

    while True:
        print("midpoint: " + str(midpoint) + " start: " + str(start) + " end: " + str(end));
        if tosearch[midpoint] != target:
            print("at " + str(midpoint) + " we found " + str(tosearch[midpoint]) + ", the target is " + str(target));
            if tosearch[midpoint] > target:
                print("number found was larger than midpoint - searching bottom half");
                end = midpoint;
            else:
                print("number found was smaller than midpoint - searching top half");
                start = midpoint;

            midpoint = int(math.floor((end + start) / 2));
            print("new start/end/midpoint: " + str(start) + "/" + str(end) + "/" + str(midpoint));

        else:
            break;

    print("found " + str(target) + " at position " + str(midpoint));
    return midpoint;

The python code can be tested with something like this:

tosearch = [];
for i in range(50):
    tosearch.append(random.randrange(0, 75));

tosearch.sort();
tofind = random.choice(tosearch);

print("result: " + str(binarysearch(tosearch, tofind)));

That's a lot of code for one blog post.....

Art by Mythdael