My Binary Search Implementation

Question

I have implemented binary search in JavaScript.

I run it on node.

I pass an comma separated string of numbers in ascending order as first argument and the number to be searched in the second argument.

the code is as follows,

var myArray = [], 
searchNum = undefined;
// below function is used to capture the 
// commandline parameters for array and the
// number to be searched
(function(){
 process.argv.forEach(function (val, index, array) {
 var idx = 0, ar = undefined;
 try{
 if(index === 2){
 ar = val.split(",");
 // convert the numbers present as string values is array
 // to array of numbers
 for(idx = 0; idx < ar.length; idx++){
 myArray.push(parseInt(ar[idx]));
 }
 }// end of if
 // third index is the number to be searched.
 if(index === 3){
 searchNum = parseInt(val)
 }
 }catch(e){
 console.log(e)
 }
 });
})();
console.log(" SEARCH NUMBER ",searchNum," in array ",myArray);
console.log(" Number ",searchNum," "+binarySearch(myArray,searchNum));
// binary-Search implementation
function binarySearch(myArray,numberToSearch){
 var arrayLength = myArray.length,
 midIndex = parseInt(arrayLength/2), 
 subArray = undefined,
 lowerIndex = 0,
 higherIndex = 0; 
 if(myArray[midIndex] === numberToSearch){
 return "is Found";
 // search the number in left side if array
 // i.e. number is found to the left of the 
 // middle Index 
 }else if(midIndex !== 0 && myArray[midIndex] > numberToSearch){ 
 lowerIndex = 0;
 higherIndex = midIndex;
 subArray = myArray.slice(lowerIndex,higherIndex); // create the sub-array
 return binarySearch(subArray,numberToSearch); // search the number in the subarray
 // search the number in right side if array
 // i.e. number is found to the right of the 
 // middle Index 
 }else if(midIndex !== 0 && myArray[midIndex] < numberToSearch){ // search the number in right side if array
 lowerIndex = midIndex + 1;
 higherIndex = arrayLength;
 subArray = myArray.slice(lowerIndex,higherIndex); // create the sub-array
 return binarySearch(subArray,numberToSearch); // search the number in the subarray
 }else{
 return "can't be found";
 } 
}// end of binarySearch method

I run the above as follows

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node binarySearch.js 34,45,67,89,90,123,345 300
 SEARCH NUMBER 300 in array [ 34, 45, 67, 89, 90, 123, 345 ]
 Number 300 can't be found
E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node binarySearch.js 34,45,67,89,90,123,345 45
 SEARCH NUMBER 45 in array [ 34, 45, 67, 89, 90, 123, 345 ]
 Number 45 is Found
E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>

Requesting to please review my above implementation, and give your valuable feedback.

Answer 1

Ok, there are two good answers about your initialization, so let's talk the binary search proper. I'll mostly address performance.

Array.slice is expensive

First off, the array.slice() calls. These are entirely unnecessary and very, VERY costly. (you're essentially copying every value into a new array). What you want is to pass down the whole array to the next iteration, along with the lowerIndexand higherIndex values. At each iteration, the midpoint is then lowerIndex+ (higherIndex-lowerIndex)/2.

Do I need recursion ?

Secondly, the recursion. I personally tend to shy away from recursion most of the time, mostly because it makes the code harder to explain. For a binary search it does make sense but it is still unnecessary. Granted, you can't feed it a big enough array that you overflow, but let's say someday you switch from midpoint to random point (why not :) ), then you may overflow on an unlucky day on just a million numbers !

parseInt is not Math.floor

I'd add to not use parseInt to round a number down. the line midIndex = parseInt(arrayLength/2) is inefficient, and it tells me you don't really know your way around javascript. The idiomatic call would be midIndex = Math.floor(arrayLength/2). It will run faster, and also explain to a reader that you are effectively rounding down (and it's intentional). These days, if I want to feel clever, I'll just put midIndex = arrayLength >> 1 (right-shifting by one, will halve your number AND round it down).

Example implementation

I kept the recursion, but please notice it could easily be replaced with a do{}while(lowerIndex < higherIndex) loop. I also omitted the parameter parsing, since there are two good answers on that.

//wrap binary search to print messages
function find(array, number){
 var ret = "SEARCH NUMBER " + number + " in " + array;
 var index = binarySearch(array, number);
 if(index === -1)
 ret += "\n >>> can't find it !";
 else
 ret += "\n >>> found it at index " + index;
 return ret;
}
// binary-Search implementation
// I changed the return value to an ine (to make it with Array.indexOf)
function binarySearch(sortedArray, numberToSearch, lowerIndex, higherIndex){ 
 //we accept not being called with all args (for the first call)
 //you'll often see this as "lowerIndex = lowerIndex || 0;"
 //which is slightly better IMO. But this is the more readable value
 if(lowerIndex === undefined) lowerIndex = 0;
 if(higherIndex === undefined) higherIndex = sortedArray.length -1;
 //this next line is left for you to study :)
 var midIndex = lowerIndex + ((higherIndex - lowerIndex) >> 1);
 //we get the value only once.
 var midValue = sortedArray[midIndex];
 if(midValue === numberToSearch){
 // by not using subArrays, we gain the ability to return the actual index
 return midIndex;//found it!
 }
 //I don't like using an else after if(...) return ...;
 //we already returned in the if so this is de-facto an else
 //I think this keeps the code more readable and pleasing. matter of taste.
 var lowerValue = sortedArray[lowerIndex],
 higherValue = sortedArray[higherIndex];
 if(lowerIndex >= higherIndex){
 return -1;//early out
 }
 if(midValue > numberToSearch){//we search left
 //notice we don't copy the array.
 // generally I'd just recurse here, but some code processors can optimize tail calls
 higherIndex = midIndex -1// search the number from left of 
 }else if(midValue < higherValue){ //we search right
 lowerIndex = midIndex +1;
 }else{
 //it seems we were given an unsorted array:
 //we won't catch it always, but on lucky hits :
 console.log("your array seems unsorted. can't binary search");
 return -1
 }
 // search the number in the same array, but with new bounds
 return binarySearch(sortedArray, numberToSearch, lowerIndex, higherIndex);
}// end of binarySearch method
console.log(find([1,2,3], 3));
console.log(find([1,2,3], 1));
console.log(find([1,2,3], 2));
//this should fail > unsorted
console.log(find([1,3,5,2,8,10,4,3], 3));
//this one, we should actually be able to see it failed
console.log(find([1,3,5,2,8,10,4,1], 3));
// your test cases : 
console.log(find([ 34, 45, 67, 89, 90, 123, 345 ], 300));
console.log(find([ 34, 45, 67, 89, 90, 123, 345 ], 45));
//test a big array
BIG = [0000, 0004, 0007, 0008, 0009, 0009, 0011, 0012, 0012, 0013, 0013, 0016, 0016, 0017, 0017, 0018, 0018, 0018, 0019, 0020, 0023, 0025, 0025, 0029, 0029, 0030, 0032, 0032, 0032, 0033, 0033, 0035, 0039, 0040, 0041, 0043, 0043, 0043, 0044, 0044, 0045, 0046, 0047, 0049, 0050, 0050, 0050, 0050, 0051, 0054, 0056, 0057, 0060, 0060, 0060, 0063, 0064, 0066, 0066, 0067, 0067, 0067, 0070, 0072, 0073, 0074, 0076, 0078, 0079, 0081, 0081, 0083, 0085, 0085, 0086, 0086, 0088, 0090, 0091, 0092, 0097, 0097, 0098, 0099, 0102, 0104, 0104, 0105, 0116, 0119, 0120, 0120, 0120, 0121, 0121, 0123, 0124, 0128, 0131, 0131, 0131, 0133, 0134, 0135, 0136, 0137, 0137, 0138, 0138, 0138, 0141, 0142, 0145, 0145, 0147, 0147, 0148, 0148, 0150, 0151, 0152, 0153, 0154, 0154, 0156, 0157, 0157, 0158, 0158, 0159, 0160, 0161, 0161, 0161, 0162, 0162, 0163, 0163, 0165, 0165, 0166, 0166, 0166, 0168, 0169, 0170, 0170, 0171, 0171, 0174, 0177, 0178, 0178, 0179, 0179, 0180, 0181, 0185, 0185, 0186, 0186, 0186, 0187, 0190, 0192, 0192, 0194, 0194, 0195, 0195, 0196, 0197, 0197, 0197, 0199, 0200, 0200, 0201, 0201, 0202, 0204, 0205, 0206, 0206, 0206, 0206, 0207, 0207, 0207, 0208, 0210, 0211, 0211, 0214, 0215, 0218, 0221, 0221, 0222, 0222, 0223, 0226, 0226, 0258, 0258, 0259, 0263, 0263, 0263, 0264, 0267, 0269, 0269, 0271, 0274, 0275, 0278, 0282, 0282, 0288, 0288, 0288, 0289, 0289, 0289, 0290, 0292, 0292, 0295, 0295, 0296, 0296, 0297, 0297, 0612, 0612, 0613, 0614, 0614, 0615, 0615, 0616, 0616, 0617, 0618, 0618, 0618, 0620, 0620, 0621, 0622, 0623, 0626, 0626, 0627, 0629, 0629, 0629, 0630, 0638, 0638, 0639, 0642, 0643, 0644, 0645, 0646, 0647, 0647, 0647, 0647, 0647, 0648, 0648, 0649, 0650, 0650, 0652, 0653, 0653, 0653, 0655, 0655, 0659, 0659, 0659, 0661, 0661, 0662, 0663, 0663, 0665, 0666, 0667, 0668, 0668, 0673, 0673, 0674, 0674, 0675, 0676, 0677, 0677, 0678, 0679, 0679, 0680, 0680, 0681, 0681, 0682, 0682, 0684, 0685, 0686, 0686, 0688, 0688, 0688, 0695, 0695, 0696, 0697, 0698, 0699, 0702, 0702, 0704, 0704, 0705, 0706, 0709, 0709, 0714, 0717, 0717, 0719, 0719, 0720, 0720, 0721, 0721, 0722, 0723, 0723, 0724, 0724, 0725, 0726, 0726, 0728, 0731, 0731, 0732, 0733, 0733, 0734, 0736, 0736, 0737, 0737, 0738, 0742, 0742, 0743, 0744, 0745, 0745, 0746, 0746, 0746, 0747, 0752, 0752, 0753, 0754, 0756, 0757, 0757, 0758, 0759, 0759, 0760, 0764, 0764, 0765, 0765, 0766, 0767, 0767, 0768, 0772, 0774, 0774, 0776, 0777, 0778, 0779, 0779, 0780, 0780, 0780, 0780, 0781, 0781, 0782, 0783, 0785, 0787, 0788, 0788, 0792, 0797, 0797, 0799, 0799, 0800, 0800, 0801, 0801, 0801, 0803, 0804, 0807, 0807, 0808, 0809, 0809, 0810, 0811, 0811, 0811, 0812, 0813, 0814, 0814, 0814, 0814, 0815, 0816, 0818, 0820, 0821, 0821, 0822, 0823, 0823, 0824, 0824, 0824, 0824, 0825, 0827, 0829, 0830, 0831, 0833, 0834, 0838, 0838, 0838, 0840, 0840, 0841, 0842, 0843, 0843, 0845, 0845, 0848, 0849, 0850, 0852, 0852, 0852, 0853, 0857, 0857, 0859, 0859, 0861, 0861, 0862, 0862, 0863, 0863, 0864, 0865, 0865, 0865, 0865, 0866, 0867, 0868, 0868, 0869, 0869, 0870, 0872, 0873, 0873, 0873, 0873, 0874, 0875, 0875, 0875, 0878, 0880, 0882, 0884, 0886, 0888, 0891, 0893, 0893, 0893, 0895, 0896, 0896, 0897, 0897, 0898, 0898, 0900, 0900, 0900, 0900, 0900, 0902, 0902, 0903, 0904, 0904, 0905, 0906, 0906, 0907, 0907, 0910, 0910, 0911, 0911, 0912, 0913, 0913, 0914, 0914, 0914, 0915, 0915, 0916, 0916, 0917, 0918, 0920, 0920, 0920, 0922, 0923, 0923, 0924, 0924, 0924, 0924, 0926, 0927, 0930, 0931, 0932, 0933, 0933, 0934, 0934, 0935, 0936, 0937, 0937, 0938, 0938, 0939, 0940, 0940, 0941, 0941, 0942, 0944, 0945, 0945, 0946, 0947, 0947, 0947, 0948, 0948, 0949, 0952, 0953, 0954, 0958, 0958, 0959, 0959, 0960, 0961, 0962, 0962, 0963, 0964, 0964, 0968, 0969, 0969, 0971, 0972, 0974, 0974, 0976, 0977, 0978, 0981, 0981, 0981, 0982, 0983, 0985, 0987, 0988, 0990, 0991, 0991, 0993, 0996, 0996, 0996, 0996, 0996, 0997, 0997, 0998, 0998, 0998, 0999];
console.log("searching big array");
console.log("300 ? : ", binarySearch(BIG, 300));
console.log("45 ? : ", binarySearch(BIG, 45));
console.log("959 ? : ", binarySearch(BIG, 959));

appendix : do I need a search at all ?

As a side note, please keep in mind that a binary search will only work on a sorted list, so you'd need to check for that when parsing the input, OR sort it before calling binary search. So as an exercise, your code is fine, but in production code, I'd be pissed if you didn't just compare and return while parsing the input.

• Rahul Shivsharan: Thanks for your valuable reply on my question. Can you please show me how you will be able to implement the same program in more effective way. I am more interested in removing the "array.slice()" part. Thanks
• Boris: OK, I'll do that

Answer 2

Just focusing on the initialization part.

• The code is using both index and idx which gives off a code smell, something could be better there
• The code is using idx just to loop over an array, apply a function and push. We can do better than this

• Comments should be useful, commenting the end of an if statement is not useful

  (function(){
   process.argv.forEach(function (val, index, array) {
   try{
   //Add the comma separated numbers to myArray as integers 
   if(index === 2){
   myArray = myArray.concat( val.split(",").map(c=>parseInt(c)) );
   } else if (index === 3){
   //Third index is the number to be searched.
   searchNum = parseInt(val)
   }
   }catch(e){
   console.log(e)
   }
   });
  })();
  

If you think further, then we could skip the whole loop business, and just access the 2 values we need. It would be simpler, and better.

 (function(){
 var args = process.argv;
 try{
 //Add the comma separated numbers to list as integers 
 list = list.concat( args[2].split(",").map(c=>parseInt(c)) );
 //Third index is the number to be searched.
 searchNum = parseInt( args[3] );
 }catch(e){
 console.log(e)
 }
 })();

myArray is not a great name, I preferred list.

Answer 3

Processing command line arguments

Looping is not suitable for processing command line arguments when each position means something different, as in this program:

• comma separated values
• value to search

Consider this alternative:

function parseArgs(args) {
 if (args.length != 4) {
 console.log("usage: node script.js values_csv value");
 return null;
 }
 return {
 nums: args[2].split(",").map(x => parseInt(x, 10)),
 value: parseInt(args[3])
 };
}

You could call this with parseArgs(process.argv), and since process.argv is a parameter, you could unit test the implementation to verify it actually works.

Note that although you wrapped much of the command line argument parsing logic in a try-catch, I don't see why. The only suspicious point I see is parseInt, but that returns NaN if it cannot parse a number, it won't throw an exception.

Specify radix when using parseInt

It's strongly recommended to specify the radix parameter when using parseInt.