This is a little more complicated than most things on small-code.blogspot.com. There are two files, one is plain html with some javascript/ajax in it, and the other is a cgi.pm (C-G-I-Perl-Module) file that relies on your webserver properly serving perl scripts to the web.
My coding is based on a perl script I found on the web written by my first computer science instructor, Jonathan Jacky. His script is here.
Source code: bsearch subroutine
sub bsearch {
my ($searchterm, $a) = @_;
my ($lower, $upper) = (0, @ - 1);
my $index;
while ($lower <= $upper) {
$index = int(($lower + $upper)/2);
print " looking for at index=$index point in between upper= and lower=$lower\n";
if ($searchterm > $a->[$index] ) {$lower = $index+1;}
elsif ($searchterm < $a->[$index] ) { $upper = $index-1; }
else {return "found at line $index\n"; }
}
return "did not find: $searchterm\n";
$results=bsearch($searchword,\@sortedNums);
print $results;
}
search.html
<html>
<head>
<title>Binary Search Perl CGI.pm</title>
<script language="Javascript">
function xmlhttpPost(strURL) {
var xmlHttpReq = false;
var self = this;
// Mozilla/Safari
if (window.XMLHttpRequest) {
self.xmlHttpReq = new XMLHttpRequest();
}
// IE
else if (window.ActiveXObject) {
self.xmlHttpReq = new ActiveXObject("Microsoft.XMLHTTP");
}
self.xmlHttpReq.open('POST', strURL, true);
self.xmlHttpReq.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded');
self.xmlHttpReq.onreadystatechange = function() {
if (self.xmlHttpReq.readyState == 4) {
updatepage(self.xmlHttpReq.responseText);
}
}
self.xmlHttpReq.send(getquerystring());
}
function getquerystring() {
var form = document.forms['f1'];
var searchterm = form.searchterm.value;
qstr = 'w=' + escape(searchterm); // NOTE: no '?' before querystring
return qstr;
}
function updatepage(str){
document.getElementById("result").value = str;
}
</script>
</head>
<body>
<h5>Lance Miller's fun with binary search with Perl CGI module</h5>
<form name="f1">
<p>search term: <input name="searchterm" type="text" value="62303311"></input>
<input value="search" type="button" onclick='JavaScript:xmlhttpPost("search.pl")' onload='JavaScript:xmlhttpPost("search.pl")'>
</p>
<p><b>bsearch</b> subroutine is the core processing code in the server side perl script which sends plain text to this
page's ajax powered javascript.</p>
<pre>
sub bsearch {
my ($searchterm, $a) = @_;
my ($lower, $upper) = (0, @ - 1);
my $index;
while ($lower <= $upper) {
$index = int(($lower + $upper)/2);
print " looking for at index=$index point in between upper= and lower=$lower\n";
if ($searchterm > $a->[$index] ) {$lower = $index+1;}
elsif ($searchterm < $a->[$index] ) { $upper = $index-1; }
else {return "found at line $index\n"; }
}
return "did not find: $searchterm\n";
$results=bsearch($searchword,\@sortedNums);
print $results;
}
</pre>
<div>
<br /><hr />
<textarea name="result" id="result" cols="140" rows="1000" scroll="yes" wrap="false"></textarea>
</div>
</form>
</body>
</html>
search.pl
#!/usr/bin/perl -w
use CGI;
use Time::HiRes;
$query = new CGI;
$searchword = $query->param('w');
$remotehost = $query->remote_host();
print $query->header;
$mytime=localtime;
loadArray();
sub loadArray {
@randomArray= (
"99884558",
"12818457",
"57978287",
"80679998",
"81303222",
"88621216",
"44913561",
"28114899",
"82977136",
"70551898",
"96350125",
"26897961",
"46830924",
"36044684",
"42834719",
"88961252",
"41790591",
"61873403",
"22431869",
"47438295",
"24847842",
"14577888",
"35200952",
"44220336",
"70100458",
"63085933",
"86282491",
"99533253",
"09606957",
"26034142",
"93138243",
"44042626",
"78027817",
"95596538",
"40287838",
"19490936",
"46403564",
"56726408",
"42105575",
"69488869",
"03687365",
"87610675",
"05981774",
"58369886",
"96835842",
"36738419",
"71274210",
"24520911",
"64788741",
"40151782",
"70354978",
"94359447",
"36165315",
"10014350",
"32517195",
"50210264",
"39334533",
"61385098",
"29101776",
"59219760",
"11384710",
"58970881",
"72601327",
"50786839",
"49107446",
"17273946",
"74325878",
"07433704",
"11391759",
"74435593",
"46669569",
"94159681",
"09289902",
"27369091",
"45030626",
"79245943",
"87420459",
"39055791",
"10578194",
"15662388",
"06526033",
"94628324",
"48604281",
"44331199",
"59710199",
"69737571",
"04236268",
"18985199",
"05858530",
"86624944",
"78581173",
"43803811",
"37060365",
"01104467",
"28615419",
"97957200",
"70096891",
"07057563",
"12445294",
"28036354",
"10320028",
"77906526",
"52886381",
"62637142",
"52656168",
"92824899",
"60038197",
"97247120",
"93108917",
"21585071",
"25846395",
"40264947",
"65230783",
"29575635",
"29140301",
"33618378",
"18420012",
"86075613",
"30948880",
"27966351",
"77210191",
"70000716",
"65269496",
"19486719",
"43614339",
"99787163",
"79110172",
"54273736",
"76534547",
"82339810",
"72816078",
"54100234",
"22582456",
"67006266",
"54900790",
"66454859",
"61700876",
"97869281",
"91129290",
"30022303",
"26749585",
"35702880",
"03491356",
"38671554",
"12200330",
"11950784",
"56779635",
"40962294",
"76120675",
"56312052",
"39296918",
"80648644",
"13141550",
"63994419",
"76166835",
"63611692",
"17357418",
"60490258",
"01911604",
"36400032",
"13739396",
"65574190",
"46806517",
"19233159",
"97672379",
"30818802",
"35319711",
"06166998",
"97214970",
"63464151",
"36999445",
"66820748",
"27606344",
"04552780",
"31081344",
"45698509",
"43527053",
"72217282",
"58489967",
"57576995",
"42753801",
"26540797",
"21023614",
"09078885",
"33425533",
"52546714",
"20917283",
"62534955",
"77487482",
"03021801",
"99006552",
"72681013",
"65984301",
"79023778",
"10590149",
"93690465",
"69285240",
"06033266",
"41182271",
"50009087",
"23479413",
"68739273",
"85968423",
"03984256",
"03270686",
"71287104",
"55693286",
"73001598",
"57187934",
"77088339",
"99153509",
"36859861",
"25565299",
"54517311",
"35984833",
"12862516",
"96467460",
"27314950",
"19656592",
"84564483",
"79966112",
"01388731",
"25049704",
"15696139",
"39722918",
"22080694",
"45668620",
"47334834",
"86945493",
"77950187",
"23749081",
"76593888",
"11185649",
"34320352",
"76220131",
"83124024",
"67549502",
"79348969",
"85612518",
"81958271",
"42047181",
"02138828",
"58731860",
"90757392",
"26055543",
"18294753",
"16550520",
"68997179",
"11557859",
"89236032",
"78761119",
"45078344",
"58350793",
"41448389",
"93928051",
"05611954",
"74822165",
"32493920",
"64859557",
"43629386",
"40294933",
"24735899",
"17790046",
"69668958",
"65646620",
"14662463",
"67771647",
"88873458",
"12498891",
"39826013",
"10131616",
"37950097",
"47579656",
"60554776",
"66799345",
"72659453",
"34980725",
"27037165",
"52907131",
"99112160",
"93202950",
"13324446",
"96271437",
"30291028",
"22606798",
"73129253",
"64496034",
"04108924",
"47779603",
"41901458",
"14190491",
"06895112",
"15508206",
"86588952",
"48276791",
"60120265",
"48712723",
"81915894",
"10159578",
"55809475",
"83468225",
"67467269",
"17469453",
"70525212",
"57201779",
"45660393",
"73933362",
"94260989",
"07848329",
"30319406",
"89138830",
"30731527",
"21932692",
"89661781",
"26143064",
"43355681",
"54467376",
"94608179",
"42003360",
"50892424",
"82545058",
"79868219",
"89424248",
"26531899",
"01625928",
"84607058",
"13877889",
"42448987",
"96274298",
"85582053",
"89902731",
"58405578",
"40043703",
"38088086",
"55745545",
"75754224",
"15430550",
"10110139",
"85800350",
"66874848",
"11197847",
"56485414",
"22829883",
"42852222",
"36272263",
"61935365",
"70881674",
"83340724",
"16035468",
"52328511",
"37386225",
"69860335",
"73649867",
"59896839",
"21073181",
"90897731",
"21077118",
"21050014",
"27353748",
"61895272",
"68669372",
"82470046",
"75925414",
"11079208",
"05273606",
"49965430",
"82107452",
"06218056",
"78638220",
"75567215",
"51477807",
"57419681",
"08598784",
"40740681",
"35757286",
"67917847",
"10210077",
"86763978",
"10222569",
"95974084",
"37703286",
"10770368",
"49127624",
"61927740",
"19679441",
"01174699",
"49310345",
"74987381",
"54164360",
"69183870",
"15579205",
"31803967",
"66551329",
"90202879",
"73676886",
"53602130",
"97203271",
"40794506",
"66968417",
"01654601",
"80883022",
"52744825",
"54170259",
"47235311",
"88627940",
"21140468",
"19967309",
"76223038",
"62803376",
"63153101",
"11573556",
"89034755",
"70003119",
"77655378",
"85501387",
"66281917",
"79780144",
"51412711",
"77562251",
"70460868",
"37163781",
"58789973",
"43206842",
"85659318",
"36933878",
"42776360",
"13558719",
"19037181",
"21137063",
"27303852",
"66937717",
"81834164",
"64989175",
"12233459",
"96651230",
"78166112",
"44255175",
"67243983",
"65363826",
"68637764",
"97186698",
"09657998",
"35679132",
"01873622",
"64982972",
"33306987",
"79786554",
"38701074",
"59650212",
"54629983",
"47570198",
"77980656",
"02810319",
"74713746",
"56552535",
"43597449",
"32574104",
"49488478",
"66048941",
"88581665",
"14660958",
"48725579",
"26443612",
"46674982",
"61927422",
"52835937",
"11905650",
"32292473",
"69643034",
"53148655",
"98179402",
"25683135",
"41645954",
"82556697",
"99496693",
"44128660",
"05344924",
"39184467",
"43340024",
"27787436",
"29215486",
"81782265",
"49731355",
"55906517",
"34223704",
"12352274",
"39200770",
"20845173",
"15443882",
"93025821",
"27755199",
"71412350",
"23086492",
"52908854",
"61599905",
"12557072",
"06325641",
"61838228",
"73100722",
"37751111",
"41748442",
"71575071",
"54110895",
"11821200",
"37324038",
"18952990",
"91246401",
"29364083",
"12378641",
"28991829",
"44396893",
"51490442",
"82602819",
"84510718",
"38624350",
"15275070",
"40271816",
"67290538",
"46583935",
"00761280",
"45512407",
"16322241",
"47549065",
"86317565",
"48869832",
"37739949",
"13899084",
"70839001",
"92698949",
"25773872",
"43543337",
"28092693",
"62282635",
"84788793",
"68360195",
"81094209",
"37030783",
"49456949",
"32182567",
"12609403",
"22390990",
"09052557",
"04494060",
"22537799",
"11808160",
"22525967",
"80927779",
"40607900",
"86981469",
"40176508",
"52181474",
"91985438",
"95394726",
"37414873",
"05394176",
"97163703",
"51693649",
"99390450",
"83073964",
"15353021",
"80013098",
"79191925",
"52736452",
"55329950",
"50908185",
"92769085",
"85254897",
"45064919",
"62660538",
"45477908",
"03383044",
"04528835",
"23798571",
"73772859",
"00269767",
"21967677",
"72626494",
"23933978",
"21181399",
"44455324",
"91998266",
"67601477",
"99392272",
"18794814",
"64201695",
"09117275",
"18513109",
"54506246",
"04233862",
"91065484",
"35173669",
"49882491",
"75757803",
"63472419",
"10842839",
"21363391",
"07040513",
"92867606",
"80009289",
"62792097",
"82711149",
"39770946",
"46240321",
"16198004",
"32673889",
"32571840",
"51578488",
"16666886",
"18715890",
"58305041",
"52563812",
"74476445",
"78378110",
"48950845",
"21181326",
"17599516",
"86421960",
"05877212",
"93808397",
"38124549",
"18114094",
"15181841",
"67281738",
"11033238",
"41999533",
"22661675",
"92919805",
"05096212",
"21089751",
"47676568",
"14777571",
"82728975",
"34713295",
"52881493",
"01873484",
"95390860",
"14255586",
"45061144",
"09505664",
"14386242",
"65139875",
"81479152",
"91148171",
"83278034",
"28632509",
"38713199",
"13388041",
"71886395",
"04474819",
"98271351",
"54549120",
"41931930",
"66478955",
"56247399",
"82552158",
"03131867",
"05669110",
"87746973",
"95776486",
"00263664",
"65386456",
"52849816",
"63767635",
"17110409",
"66118393",
"10489638",
"14735323",
"51176730",
"65781898",
"33491972",
"70527181",
"38978735",
"28146287",
"12218503",
"79255754",
"15871185",
"01393285",
"44357970",
"09364834",
"47434166",
"28488085",
"05212875",
"74928560",
"76954459",
"47791196",
"18150603",
"47825480",
"67801869",
"58940207",
"55119731",
"52316675",
"20435546",
"21083088",
"68067720",
"49508043",
"33497534",
"28487354",
"42893796",
"27485024",
"37422028",
"47305652",
"56417269",
"28879225",
"84878455",
"64321176",
"12076893",
"90453777",
"56333590",
"17309031",
"47669363",
"27008955",
"71649893",
"48860847",
"18083834",
"16534961",
"13280843",
"02420928",
"65804356",
"53570148",
"91401764",
"45170423",
"81806503",
"61562059",
"89934153",
"48686449",
"73923487",
"33397945",
"02936961",
"76077808",
"33901162",
"13229735",
"49617073",
"88424495",
"16413743",
"09325119",
"30762507",
"01011209",
"31112130",
"33533295",
"49045254",
"57988703",
"78472805",
"49758534",
"06547887",
"96626962",
"34307686",
"82104611",
"71148169",
"10748772",
"02619656",
"68622879",
"74966597",
"65570379",
"97009549",
"54365501",
"38731744",
"63541597",
"12828751",
"44381774",
"04954541",
"96402732",
"85093152",
"55746918",
"85408772",
"76483942",
"78790195",
"84015044",
"75018060",
"05611789",
"10546509",
"55495624",
"94054596",
"99589912",
"55668552",
"18509400",
"27885394",
"69309529",
"43586319",
"46743568",
"96910667",
"24270860",
"49728142",
"12532237",
"88958883",
"05618351",
"57579868",
"43086540",
"56334807",
"83308486",
"23171823",
"74599534",
"57241235",
"81736386",
"15280993",
"86953011",
"45281527",
"39300867",
"01053789",
"32793040",
"96302799",
"42829170",
"16749936",
"52868587",
"89480885",
"41968815",
"88101206",
"66949454",
"61038948",
"25921701",
"65441012",
"61903893",
"94958162",
"41203628",
"87967889",
"74686899",
"65999832",
"82348424",
"33928094",
"42283834",
"83043445",
"15334230",
"18178678",
"38809866",
"09173891",
"50016384",
"88503162",
"24564119",
"16556578",
"13715754",
"92584907",
"42685479",
"30410969",
"20023583",
"83504721",
"00618142",
"98721083",
"76685979",
"67144894",
"29018963",
"44553339",
"70253879",
"09211960",
"90864247",
"07045075",
"12518024",
"48816255",
"65134264",
"15798844",
"07522932",
"39508023",
"14764367",
"71818432",
"52512893",
"91407509",
"91842903",
"36856525",
"89830252",
"17893016",
"93720954",
"33143281",
"57160879",
"85299393",
"78016801",
"92573695",
"75559323",
"59630982",
"56210270",
"05469746",
"44945212",
"33295205",
"43705557",
"33628426",
"53284792",
"33792315",
"38233847",
"54341287",
"92993288",
"63847848",
"92996565",
"18308272",
"26587738",
"07159505",
"01740814",
"86392552",
"79550935",
"55251524",
"25638341",
"41599591",
"11561568",
"97507722",
"33770120",
"87257359",
"84580590",
"73717222",
"91242781",
"53800717",
"27602103",
"64286062",
"53028346",
"00361587",
"31848061",
"79395873",
"56516277",
"97499361",
"78537220",
"55820438",
"99143861",
"12605638",
"62038468",
"16921751",
"50877668",
"65714118",
"04868523",
"51017752",
"51805292",
"33392340",
"98011554",
"20223982",
"89363357",
"36922866",
"07379785",
"04776970",
"56701746",
"99406523",
"22486203",
"19988772",
"56097678",
"90924156",
"99156361",
"13540846",
"10559127",
"47153822",
"37539876",
"17653868",
"99252141",
"76844726",
"46152660",
"22974672",
"28801945",
"59359503",
"19982781",
"29257842",
"75274586",
"94038554",
"61453489",
"35429558",
"55423352",
"90631108",
"71534761",
"66391781",
"09737950",
"51351534",
"51473125",
"62490300",
"02926132",
"48364918",
"79868961",
"69632701",
"70212169",
"65042783",
"98773409",
"60516504",
"06414781",
"66522186",
"27396385",
"80720157",
"62123297",
"43243827",
"59184315",
"92892867",
"86091401",
"18732667",
"54749806",
"09060410",
"86693233",
"66276259",
"12477225",
"21119479",
"06252561",
"25448185",
"86645561",
"79505371",
"54438897",
"83690327",
"34452845",
"72914399",
"71725698",
"54679267",
"82538042",
"52893594",
"76673554",
"22111207",
"97720862",
"26867281",
"80511421",
"54558279",
"20854194",
"37611002",
"62303311",
"35723621",
"95272931",
"68872035",
"27361197",
"97372964",
"39577239",
"15285988",
"10116181",
"46930229",
"82474964",
"01849297",
"12552124",
"03572884",
"23968687",
"11880317",
"70428500",
"75027593",
"63279821",
"25617945",
"91055769",
"08053998",
"80653886",
"25246206",
"59468031",
"69000196");
my $start = [ Time::HiRes::gettimeofday( ) ];
@sortedNums = sort { $a <=> $b } @randomArray; # numerical sort
my $elapsed = Time::HiRes::tv_interval( $start );
$sortElapsedTimeText="\tsort elapsed time: $elapsed seconds\n";
my $startBsearch = [ Time::HiRes::gettimeofday( ) ];
$results=bsearch($searchword,\@sortedNums);
my $elapsedBsearch = Time::HiRes::tv_interval( $startBsearch );
print "\t$results\n";
print $sortElapsedTimeText;
print "\tsearch elapsed time: $elapsedBsearch seconds\n";
print "\n\tbelow is the sorted list of numbers you searched against:\n\n";
foreach (@sortedNums) { print "\t\t\t$_\n";}
}
sub bsearch {
my ($searchterm, $a) = @_;
my ($lower, $upper) = (0, @$a - 1);
my $index;
while ($lower <= $upper) {
$index = int(($lower + $upper)/2);
print "\tlooking for $searchterm at index=$index point in between upper=$upper and lower=$lower\n";
if ($searchterm > $a->[$index] ) {$lower = $index+1;}
elsif ($searchterm < $a->[$index] ) { $upper = $index-1; }
else {return "\n\t\t>>> found $searchterm at line $index\n"; }
}
return "\n\t\t>>> did not find: $searchterm\n";
}
No comments:
Post a Comment