3

バックグラウンド

私は現在このような配列を持っています：

[1,1,2,3,4,5,5,5,6,7,8,8,8,8,9,10]

私はこのウェブサイトから素晴らしいJSバイナリ検索式を使用しています：

searchArray = function(needle, haystack, case_insensitive) {
    if (typeof(haystack) === 'undefined' || !haystack.length) return -1;
    
    var high = haystack.length - 1;
    var low = 0;
    case_insensitive = (typeof(case_insensitive) === 'undefined' || case_insensitive) ? true:false;
    needle = (case_insensitive) ? needle.toLowerCase():needle;
    
    while (low <= high) {
        mid = parseInt((low + high) / 2)
        element = (case_insensitive) ? haystack[mid].toLowerCase():haystack[mid];
        if (element > needle) {
            high = mid - 1;
        } else if (element < needle) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    
    return -1;
};

これは、単一の値を返す場合に正常に機能します。

質問

単一の値ではなく範囲を返すにはどうすればよいですか？たとえば8、配列からすべての値を返すにはどうすればよいでしょうか。ただし、それでもバイナリ検索を使用します（すべてをループしたくない!!）。

ありがとう！

4

2 に答える 2

3

このようなもの？http://jsfiddle.net/DCLey/3/

var arr = ['1','1','2','3','4','5','5','5','6','7','8','8','8','8','9','10'];
        //  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15            
var searchArray = function(needle, haystack, case_insensitive) {
    if (typeof(haystack) === 'undefined' || !haystack.length) return -1;

    var high = haystack.length - 1;
    var low = 0;
    var vals = []; 
    var bUp = true; 
    var bDown = true;
    var i = 1; 
    case_insensitive = (typeof(case_insensitive) === 'undefined' || case_insensitive) ? true:false;
    needle = (case_insensitive) ? needle.toLowerCase():needle;

    while (low <= high) {
        mid = parseInt((low + high) / 2)
        element = (case_insensitive) ? haystack[mid].toLowerCase():haystack[mid];
        if (element > needle) {
            high = mid - 1;
        } else if (element < needle) {
            low = mid + 1;
        } else {
            vals.push(mid); 
            while(bUp || bDown){
                if(bUp && haystack[mid] === haystack[mid + i]){
                    vals.push(mid + i); 
                }else{
                    bUp = false;   
                }
                if(bDown && haystack[mid] === haystack[mid - i]){
                    vals.push(mid - i); 
                }else{
                    bDown = false;   
                }
                i++;
            }
            return vals; 
        }
    }

    return -1;
};

alert(searchArray('8', arr, true));
于 2012-04-10T17:01:30.077 に答える
0

特定の数値のインスタンス数を数えたいだけでない限り、配列内の数値の上限と下限のインデックスを返す必要があります。2 つのアプローチから選択できます。

  1. 上限と下限のインデックスを配列として返すバイナリ検索を作成します
  2. 下限を返す標準のバイナリ検索に固執し、実行の最後に到達するまで単純に繰り返します。

アプローチ 2 を使用すると、パフォーマンスがわずかに低下しますが、一般的なアルゴリズムは維持されます。

于 2012-04-10T18:45:17.310 に答える