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