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.

  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.