-
-
Save binarymax/995468 to your computer and use it in GitHub Desktop.
Binary Search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * | |
| * Binary Search algorithm | |
| * pass in sorted array 'a', and item to find 'b' | |
| * returns the index if found, -1 otherwise (same as Array indexOf) | |
| * | |
| */ | |
| function( | |
| a, //Array parameter | |
| b, //Item to find | |
| c, //placeholder: lower bound | |
| d, //placeholder: upper bound | |
| e //placeholder: current index | |
| ){ | |
| for(c=0,d=a.length; //init lower and upper bounds | |
| c<=d; //until lower and upper converge | |
| ){ | |
| if(b>a[e=0|(c+d)/2])c=e+1; //set index to halfway between upper and lower bounds. | |
| //if index is less than the item, increase the lower bound. | |
| else d=(b==a[e])?-2:e-1 //else if item found, set a flag(-2) and exit, otherwise decrease upper bound | |
| } | |
| return(d>-2)?-1:e //if flagged (-2), return the index, otherwise return -1 | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!doctype html> | |
| <html> | |
| <head> | |
| <title>Example</title> | |
| <meta charset="utf-8" /> | |
| <script language="javascript" type="text/javascript"> | |
| var f = function(a,b,c,d,e){for(c=0,d=a.length;c<=d;){if(b>a[e=0|(c+d)/2])c=e+1;else d=(b==a[e])?-2:e-1}return(d>-2)?-1:e} | |
| //load up a big sorted array: | |
| for(var i=0,l=10000000,a=[],N=0;i<l;i++) a.push(i); | |
| //Tests: | |
| //binary search existing | |
| N = f(a,l-92384); | |
| console.log(N); | |
| //indexOf existing | |
| N = a.indexOf(l-92384); | |
| console.log(N); | |
| //binary search non-existing | |
| N = f(a,-5); | |
| console.log(N); | |
| //indexOf non-existing | |
| N = a.indexOf(-5); | |
| console.log(N); | |
| </script> | |
| </head> | |
| <body> | |
| <div>Hi!</div> | |
| </body> | |
| </html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function(a,b,c,d,e){for(c=0,d=a.length;c<=d;){if(b>a[e=0|(c+d)/2])c=e+1;else d=(b==a[e])?-2:e-1}return(d>-2)?-1:e} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| Version 2, December 2004 | |
| Copyright (C) 2011 Max Lovenheim Irwin <http://binarymax.com> | |
| Everyone is permitted to copy and distribute verbatim or modified | |
| copies of this license document, and changing it is allowed as long | |
| as the name is changed. | |
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
| 0. You just DO WHAT THE FUCK YOU WANT TO. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "name": "Binary Search", | |
| "description": "Binary Search for sorted array.", | |
| "keywords": [ | |
| "binarysearch", | |
| "search", | |
| "find", | |
| "indexOf" | |
| ] | |
| } |
Oooops. Thanks Yaffle! Good thing I have 25 bytes to spare so I can fix it. I'll get to it this week.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
var test = [1,1,1,1];
console.log(f(test,1));
console.log(test.indexOf(1));