advanced code snippet search

Posted By

jatkins on 04/27/12


Tagged

search array binary algorithm find binarysearch


Versions (?)

Who likes this?

2 people have marked this snippet as a favorite

chrisaiv
hurcy


JavaScript Binary Search

 / Published in: JavaScript
 

Released into the public domain.

Expand | Embed | Plain Text 
  1. function binarySearch(needleValue, arrayHaystack) {
  2. 	var lowerBound, upperBound, midpointIndex, midpointValue;
  3. 	lowerBound = 0;
  4. 	upperBound = arrayHaystack.length - 1;
  5. 	midpointIndex = Math.ceil((upperBound+lowerBound)/2);
  6. 	midpointValue = arrayHaystack[midpointIndex];
  7. 	while(midpointIndex>=0&&midpointIndex<arrayHaystack.length&&midpointValue!=needleValue) {
  8. 		if(arrayHaystack[lowerBound]==needleValue) {
  9. 			midpointIndex = lowerBound;
  10. 			midpointValue = arrayHaystack[midpointIndex];
  11. 			break;
  12. 		}
  13. 		else if(arrayHaystack[upperBound]==needleValue) {
  14. 			midpointIndex = upperBound;
  15. 			midpointValue = arrayHaystack[midpointIndex];
  16. 			break;
  17. 		}
  18. 		else {
  19. 			midpointIndex = Math.ceil((upperBound+lowerBound)/2);
  20. 			midpointValue = arrayHaystack[midpointIndex];
  21. 			if(needleValue>midpointValue) // in the second half
  22. 				lowerBound = midpointIndex + 1;
  23. 			else if(needleValue<midpointValue) // in the first half
  24. 				upperBound = midpointIndex - 1;
  25. 		}
  26. 		midpointValue = arrayHaystack[midpointIndex];
  27. 		if(lowerBound>upperBound) {
  28. 			midpointValue = undefined;
  29. 			break;
  30. 		}
  31. 	}
  32.  
  33. 	arrayHaystack = null;
  34. 	lowerBound = null;
  35. 	upperBound = null;
  36.  
  37. 	if(typeof midpointValue=='undefined') {
  38. 		midpointIndex = null;
  39. 		midpointValue = null;
  40. 		return -1; // not found
  41. 	}
  42. 	else {
  43. 		midpointValue = null;
  44. 		return midpointIndex; // found at arrayHaystack[midpointIndex]
  45. 	}
  46. }

Report this snippet  

You need to login to post a comment.