模式匹配在JavaScript中搜索

Question

我正在嘗試使用模式匹配的JavaScript中的二進制搜索。但問題在很多情況下都是失敗的。

我試過這段代碼。

function binarySearch(ar, el, compare_fn) { 
    var m = 0; 
    var n = ar.length - 1; 
    while (m <= n) { 
     var k = parseInt((n + m)/2); 
     var cmp = compare_fn(el, ar[k]); 
     if (cmp > 0) { 
      m = k + 1; 
      console.log(cmp,m,ar[m],k) 
     } else if(cmp < 0) { 
      n = k - 1; 
      console.log(cmp,n,ar[n],k) 
     } else { 
      return k; 
     } 
    } 
    return -m - 1; 
} 

function compare_number(a, b) { 
    var regExp = new RegExp(a, 'gi'); 
    var match= (regExp.test(b)?0:1); 
    if(match){ 
    match=a.localeCompare(b); 
    } 
    return(match); 
} 

new function test() { 
    var ar = ["job0000ya","job0002","job003","hello","myui",]; 
    var n = binarySearch(ar, "ya", compare_number); 
    console.log([n]); 
}(); 

但似乎它在這種特殊情況下的失敗。建議我可以使它成爲可能。

Answer 1

//The binary search algorithm 
 
var binarySearch = (function() { 
 
    /** 
 
    * compare_complex 
 
    * 
 
    * @param {(number | string)} a 
 
    * @param {(number | string)} b 
 
    * @returns {number} 
 
    */ 
 
    function compare_complex(a, b) { 
 
    return a.toString().localeCompare(b.toString()); 
 
    } 
 
    /** 
 
    * compare_number 
 
    * 
 
    * @param {number} a 
 
    * @param {number} b 
 
    * @returns {number} 
 
    */ 
 
    function compare_number(a, b) { 
 
    return a - b; 
 
    } 
 
    /** 
 
    * binarySearch 
 
    * 
 
    * @param {IBinarySearch} [args={ list: [], target: '' }] 
 
    * @returns {number} 
 
    */ 
 
    function binarySearch(args) { 
 
    if (args === void 0) { 
 
     args = { 
 
     list: [], 
 
     target: '' 
 
     }; 
 
    } 
 
    var params = { 
 
     list: [], 
 
     target: '', 
 
     searchThreshold: 10, 
 
     complex: false 
 
    }; 
 
    for (var key in args) { 
 
     if (args.hasOwnProperty(key) && params.hasOwnProperty(key)) { 
 
     params[key] = args[key]; 
 
     } 
 
    } 
 
    var max = params.list.length - 1; 
 
    var min = 0; 
 
    if (params.list[min] == params.target) { 
 
     return min; 
 
    } 
 
    if (params.list[max] == params.target) { 
 
     return max; 
 
    } 
 
    var compare = (params.complex === true ? compare_complex : compare_number); 
 
    while (max - min >= params.searchThreshold) { 
 
     var diff = max - Math.floor((max - min)/2); 
 
     var cmp = compare(params.list[diff], params.target); 
 
     if (cmp == 0) { 
 
     return diff; 
 
     } else if (cmp < 0) { 
 
     min = diff; 
 
     } else { 
 
     max = diff; 
 
     } 
 
    } 
 
    return params.list.slice(min, max).indexOf(params.target) + min; 
 
    } 
 
    return binarySearch; 
 
})(); 
 
//------------SIMULATION------------// 
 
//Global compare function for sorting 
 
function compare_complex(a, b) { 
 
    return a.toString().localeCompare(b.toString()); 
 
} 
 
//Test array 
 
var arr = []; 
 
//Minimum test array length 
 
var arrLength = 1000000; 
 
//Populate 
 
while (arr.length < arrLength) { 
 
    arr = arr.concat(arr, ["job0000ya", "job0002", "job003", "hello", "myui"]); 
 
} 
 
//Target to find in haystack 
 
var target = "job033"; 
 
//Add target to list 
 
arr.push(target); 
 
//Sort list (must be done before search) 
 
arr = arr.sort(compare_complex); 
 
//Actual test 
 
setTimeout(function() { 
 
    console.log("Looking for:", target, "among", arr.length, "rows"); 
 
    var t = Date.now(); 
 
    console.log("Result at index:", binarySearch({ 
 
    list: arr, 
 
    target: target, 
 
    complex: true 
 
    })); 
 
    console.log("Time(ms):", Date.now() - t); 
 
    var index = binarySearch({ 
 
    list: arr, 
 
    target: target, 
 
    complex: true 
 
    }); 
 
    console.log("5 nearest elements:", arr.slice(index - 2, index + 3)); 
 
}, 1000);