User Tools

Site Tools


λ Linear search

======= Algorithm ======= <syntax js> // Searches the array 'a' for an item 'x'. // Returns the index of 'x' or -1 if not found. function linearSearch(a, x) { for (var i=0, c=a.length; i<c; i++) { if (a[i] === x) { // Found 'x', return the index 'i'. return i; } } // Did not find 'x', return -1. return -1; } </syntax> ======= Support ======= <syntax js> function run(args) { return linearSearch(args[0], args[1]); } </syntax> ======= Tests ======= <syntax js> function testSearchOrdered() { assert( linearSearch([0,1,2,3,4,5,6,7], 5) === 5, "Index of 5 is 5."); } function testSearchUnordered() { assert( linearSearch([3,7,1,6,2,4,1,7,6,8], 1) === 2, "Index of 1 is 2 - first index."); } function testNonExist() { assert( linearSearch([0,1,2,3,4,5,6,7], 9) === -1, "Index of 9 is -1."); }</syntax> ======= Options ======= <syntax js> { "title":"Linear search", "height":"250px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script type="text/javascript"> var array = []; var hasAnswer = false; function load() { for (var i=0; i<10; i++) { array.push(Math.floor(Math.random()*50)); } var toSearchForInitial = array[Math.floor(Math.random()*array.length)]; document.getElementById('x').value = toSearchForInitial; } function update(n, x) { var element = document.getElementById("container"); var i = x.lookupInScope("i"); var arrayString = "["; for (var j=0; j<array.length;j++) { arrayString += i===j? "<span style=\"color:red\">"+ array[j]+"</span>" : array[j]; if (j < array.length-1) arrayString += ", "; } arrayString += "]"; element.innerHTML = "a = " + arrayString; if (typeof i === "number") { element.innerHTML += "<br>"+"i = "+i+(r? "<br><br>=> "+r : ""); } // print the answer var r = x.returnedValue; if (r && !hasAnswer) { hasAnswer = true; element.innerHTML += "<br><br>=> "+r; } else hasAnswer = !!r; } function args() { var toSearchFor = parseInt(document.getElementById('x').value); return [array, toSearchFor]; } </script> </head> <body onload="load()"> Search for (x): <input id="x" onchange="reset()"><br> <pre id="container"></pre> </body> </html> </syntax>

algorithm/linear_search.txt · Last modified: 2015/02/02 08:28 (external edit)