# ## 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: 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.....

## Tag Cloud

3d 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blender blog bookmarklet booting bug hunting c sharp c++ challenge chrome os cluster code codepen coding conundrums coding conundrums evolved command line compilers compiling compression containerisation css dailyprogrammer data analysis debugging demystification distributed computing dns docker documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions freeside future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs learning library linux lora low level lua maintenance manjaro minetest network networking nibriboard node.js open source operating systems optimisation own your code pepperminty wiki performance phd photos php pixelbot portable privacy problem solving programming problems project projects prolog protocol protocols pseudo 3d python reddit redis reference release releases rendering resource review rust searching secrets security series list server software sorting source code control statistics storage svg systemquery talks technical terminal textures thoughts three thing game three.js tool tutorial tutorials twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 worldeditadditions xmpp xslt

Art by Mythdael