λ Binary search

======= Algorithm ======= <syntax js> // searches the sorted array a for an item x // returns the index of x or -1 if not found function binarySearch(a, x) { var min = 0; var max = a.length-1; // continue searching while [min, max] is not empty while (min <= max) { // compute a midpoint var mid = Math.floor((min + max)/2); if (a[mid] < x) { // update min to search above mid index min = mid+1; } else if (a[mid] > x) { // update max to search below mid index max = mid-1; } else { // x found at mid index return mid; } } // did not find x, return -1 return -1; }</syntax> ======= Support ======= <syntax js> function run(args) { return binarySearch(args[0], args[1]); }</syntax> ======= Tests ======= <syntax js> function testSearch() { assert( binarySearch([0,1,2,3,4,5,6,7], 5) === 5, "Index of 5 is 5."); } function testNonExist() { assert( binarySearch([0,1,2,3,4,5,6,7], 9) === -1, "Index of 9 is -1."); }</syntax> ======= Options ======= <syntax js> { "title": "Binary search", "height": "440px" }</syntax> ======= Visualisation ======= <syntax html> <html> <head> <link rel="stylesheet" type="text/css" href="algorithms-lib/graph.css"/> <script src="http://d3js.org/d3.v2.js"></script> <script src="algorithms-lib/graph.js"></script> <script type="text/javascript"> var graph = new Graph(20); var findIdx = 10; window.onload = function() { chart = graph.createGraph(d3.select("#chart")); graphRandom(); } function graphRandom() { findIdx = Math.floor(Math.random()*graph.array.length); graph.sorted(); } function args(forCloning) { if (forCloning) { var a = graph.getClonableArray(); return [a, a[findIdx]]; } else { return [graph.array, graph.array[findIdx]]; } } function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } if (x) { graph.drawGraph(duration); drawHighlight(x); } // Highlight find bar. var bars = chart.selectAll("rect.data").data(graph.array, function(d) {return d.hash;}); bars.classed("index", function(d, i) {return i=== findIdx}); } function drawHighlight(x) { var min = x.lookupInScope("min"); var max = x.lookupInScope("max"); var idx = x.lookupInScope("x"); var bars = chart.selectAll("rect.data").data(graph.array, function(d) {return d.hash;}); bars.classed("max", function(d, i) {return i===min || i===max}); } </script> </head> <body> <div style="position:absolute;padding:2px"> <button onclick="graphRandom()">Random</button> </div> <div id="chart"></div> </body> </html></syntax>