我的二进制搜索实现

Question

我在JavaScript中实现了二进制搜索。

我在节点上运行。

我以升序传递一个逗号分隔的数字字符串，作为第一个参数和要在第二个参数中搜索的数字。

代码如下，

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

我按以下方式运行上面的代码

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>

请回顾我的上述实施情况，并给出您宝贵的反馈。

Answer 1

好的，关于初始化有两个很好的答案，所以让我们来讨论一下二进制搜索。我主要讲的是表演。

Array.slice是昂贵的

首先，array.slice()调用。这些都是完全没有必要的，而且非常、非常昂贵。(实际上是将每个值复制到一个新数组中)。您想要的是将整个数组与lowerIndex和higherIndex值一起传递到下一次迭代。在每次迭代时，中点是lowerIndex+ (higherIndex-lowerIndex)/2。

我需要递归吗?

第二，递归。大多数时候，我个人倾向于回避递归，主要是因为它使代码更难解释。对于二进制搜索，这确实是有意义的，但它仍然是不必要的。当然，您不能给它一个足够大的数组，使您溢出，但假设有一天您从中点切换到随机点(为什么不: )，那么您可能在一个不幸的日子里溢出的数字只有一百万个！

parseInt不是Math.floor

我想添加不使用parseInt来舍入一个数字。midIndex = parseInt(arrayLength/2)行效率低下，它告诉我您对javascript不太了解。惯用的称呼应该是midIndex = Math.floor(arrayLength/2)。它将运行得更快，并向读者解释你实际上是在四舍五入(这是有意的)。这些天，如果我想要聪明的话，我只会把midIndex = arrayLength >> 1 (右移1，会把你的号码减半，然后把它整下来)。

示例实现

我保留了递归，但是请注意，它可以很容易地被一个do{}while(lowerIndex < higherIndex)循环替换。我还省略了参数解析，因为有两个很好的答案。

//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));

附录:我需要搜索吗?

另外，请记住，二进制搜索只适用于排序列表，因此您需要在解析输入时检查它，或者在调用二进制搜索之前对其进行排序。因此，作为练习，您的代码很好，但是在生产代码中，如果您在解析输入时不进行比较和返回，我会很生气。

Answer 2

只关注初始化部分。

• 代码使用的是index和idx，它们散发出一种代码气味，可能会有更好的效果。
• 代码使用idx只是为了循环数组、应用函数和推送。我们可以做得比这更好
• 注释应该有用，注释if语句的结尾是无用的(function(){ process.argv.forEach(函数(val，索引，数组)){ try{ //将逗号分隔的数字作为整数添加到myArray中，如果(索引=== 2){ myArray = myArray.concat( val.split("，“).map(c=>parseInt(C )；} if (索引=== 3){ //第三个索引是要搜索的数字。searchNum = parseInt(val) }捕捉(E){ console.log(e) }；

如果您进一步考虑，那么我们可以跳过整个循环业务，只访问我们需要的两个值。它会更简单，更好。

    (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不是一个很好的名字，我更喜欢这个名字。

Answer 3

处理命令行参数

当每个位置的含义不同时，循环不适合处理命令行参数，如本程序中所示：

• 逗号分隔值
• 值要搜索

考虑这一备选办法：

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])
  };
}

您可以用parseArgs(process.argv)调用它，因为process.argv是一个参数，所以您可以对实现进行单元测试，以验证它是否有效。

请注意，尽管您将命令行参数解析逻辑包装在了一个try-catch中，但我不明白为什么。我看到的唯一可疑点是parseInt，但是它返回NaN，如果它不能解析一个数字，它不会抛出异常。

在使用parseInt

时指定基数

强烈建议在使用parseInt时指定基参数。