那些遇到过的问题

在Javascript中进行二进制搜索

4m1*_*m1r 34 javascript binary-search

我正在尝试在JavaScript中实现二进制搜索算法.事情似乎没问题,但我的回复陈述似乎是未定义的回归？谁能说出这里有什么问题？

小提琴:http://jsfiddle.net/2mBdL/

谢谢.

var a = [
    1,
    2,
    4,
    6,
    1,
    100,
    0,
    10000,
    3
];

a.sort(function (a, b) {
    return a - b;
});

console.log('a,', a);

function binarySearch(arr, i) {
    var mid = Math.floor(arr.length / 2);
    console.log(arr[mid], i);

    if (arr[mid] === i) {
        console.log('match', arr[mid], i);
        return arr[mid];
    } else if (arr[mid] < i && arr.length > 1) {
        console.log('mid lower', arr[mid], i);
        binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
    } else if (arr[mid] > i && arr.length > 1) {
        console.log('mid higher', arr[mid], i);
        binarySearch(arr.splice(0, mid), i);
    } else {
        console.log('not here', i);
        return -1;
    }

}
var result = binarySearch(a, 100);
console.log(result);
Run Code Online (Sandbox Code Playgroud)

Ale*_*hov 75

以这样的方式编写搜索函数是有用的,即如果找不到该元素,它返回一个负值,表示新元素的插入点.此外,在二进制搜索中使用递归过度且不必要.最后,通过提供比较器函数作为参数,使搜索算法通用是一种很好的做法.以下是实施.

function binarySearch(ar, el, compare_fn) {
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}
Run Code Online (Sandbox Code Playgroud)

此代码注释和单元测试在这里.

  • 返回值0不明确。元素是在列表的顶部，还是需要在列表中插入？ (3认同)
  • 您的算法返回“-m -1”，但您在 jsfiddle 中的代码注释引用了“-n -1”的返回值。可能有错别字？ (2认同)
  • 作为对怀疑者的回应，我将单元测试扩展为一组随机测试。所有的测试都通过了。查看小提琴 http://jsfiddle.net/pkfst550/48/ (2认同)
  • 返回值 0 是明确的，它明确表示“该元素在索引 0 处找到”。为了表示“该元素应该插入到索引 0 处”，该函数将返回 -1（这是 0 的 **按位补码** - "~x" == "-x-1"）。 (2认同)
  • @Rafael 好奇你为什么喜欢 `&gt;&gt; 1`？ (2认同)
  • @deb @VenkataRaju 我警告不要试图巧妙地使用“~n”。按位非运算符将其参数转换为 32 位***有符号***整数，而数组索引允许使用全范围的 32 位***无符号***整数，这意味着对于从 2 开始的所有完全有效的数组索引^31 到 2^32-1，`~n !== -n - 1`。 (2认同)

Eli*_*lka 21

您没有显式返回递归内部调用(即return binarySearch()),因此调用堆栈展开时没有返回值.像这样更新您的代码:

// ...
if (arr[mid] === i) {
    console.log('match', arr[mid], i);
    return arr[mid];
} else if (arr[mid] < i && arr.length > 1) {
    console.log('mid lower', arr[mid], i);
    return binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
} else if (arr[mid] > i && arr.length > 1) {
    console.log('mid higher', arr[mid], i);
    return binarySearch(arr.splice(0, mid), i);
} else {
// ...
Run Code Online (Sandbox Code Playgroud)

看到一个工作小提琴

  • 为什么要返回与目标匹配的值？这使整个搜索变得多余!你应该返回索引. (13认同)
  • 我建议编辑这个答案以使用“slice”而不是“splice”。人们不会期望搜索功能会改变大海捞针。我会使用“binarySearch(arr.slice(mid), i)”和“binarySearch(arr.slice(0, mid), i)”来代替。 (2认同)

jok*_*oki 15

这个问题有许多可行的解决方案,但是一旦找到匹配项,它们都会提前返回.虽然这可能对性能产生很小的积极影响,但由于二进制搜索的对数性质,这可以忽略不计,如果比较函数的计算成本很高,实际上可能会损害性能.

更重要的是,它阻止了二进制搜索算法的非常有用的应用:找到一系列匹配元素,也称为查找下限或上限.

以下实现返回指数0≤ i≤ array.length,使得在给定谓词false的array[i - 1]和true为array[i].如果谓词false无处不在,array.length则返回.

/**
 * Return 0 <= i <= array.length such that !pred(array[i - 1]) && pred(array[i]).
 */
function binarySearch(array, pred) {
    let lo = -1, hi = array.length;
    while (1 + lo < hi) {
        const mi = lo + ((hi - lo) >> 1);
        if (pred(array[mi])) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
    return hi;
}
Run Code Online (Sandbox Code Playgroud)

假设为了论证pred(array[-1]) === false和pred(array[array.length]) === true(当然,谓词从未在那些点进行评估).循环保持不变量!pred(array[lo]) && pred(array[hi]).算法在1 + lo === hi意味着!pred(array[hi - 1]) && pred(array[hi])所需的后置条件时终止.

如果阵列sort()相对于编到一个比较函数compare,该函数返回的最小 插入位置的一个item时作为调用

binarySearch(array, j => 0 <= compare(item, j));
Run Code Online (Sandbox Code Playgroud)

的插入位置是在其中,如果它在阵列中存在的物品会被发现的索引.

如下所述,以自然顺序实现数组的下限和上限很容易.

/**
 * Return i such that array[i - 1] < item <= array[i].
 */
function lowerBound(array, item) {
    return binarySearch(array, j => item <= j);
}

/**
 * Return i such that array[i - 1] <= item < array[i].
 */
function upperBound(array, item) {
    return binarySearch(array, j => item < j);
}
Run Code Online (Sandbox Code Playgroud)

当然,当数组可以包含多个相同比较的元素时,这是最有用的,例如,元素包含不属于排序条件的其他数据.

Jac*_*fin 12

? .

正确实现的二元搜索（不修改数组、制作数组的浅拷贝或其他荒谬）的平均复杂度约为O(k*log 2 (n))（其中 k 是常数表示不必要的开销）。假设您有一个包含 1024 个元素的数组，在这种情况下常数 k 为 1。使用线性搜索，平均复杂度为O(k*n/2)=O(1*1024/2)=O(512)。使用二分搜索，您的复杂度为O(k*log 2 (n))=O(1*log 2 (1024))=O(1*10)=O(10)。现在，假设你让线性搜索算法快 25%，二分搜索算法快 25%。现在，这两种算法的 k 都是 0.75。线性搜索的复杂度降低到O(384)（获得 128 个性能点），而二分搜索降低到O(7.5)（仅获得 2.5 个性能点）。优化二分搜索方法的这种最小收益是因为二分搜索方法已经非常快了。因此，任何理智的人都应该更倾向于在尝试优化二进制搜索算法之前优化程序的其余部分。尽管有这种清晰的推理，我最终还是屈服于诱惑，将二分搜索功能优化到 JavaScript 工程的绝对限制。

为了开始性能最大值，让我们首先研究我开始使用的初始函数。此函数可能比页面下方显示的函数慢得多（它仍然比此处发布的任何其他答案快得多），但它应该不那么令人困惑。

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+slowestBS(sArr, s);

function slowestBS(array, searchedValue, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start |0;
  var len = (ARG_len === void 0 ? (array.length|0)-start : ARG_len) | 0;
  len = len - 1 |0;
  for (let i=0x80000000; i; i >>>= 1) {
    if (len & i) {
      const withoutCurBit = len & ~(i-1);
      if (array[start + withoutCurBit] > searchedValue) {
        len = withoutCurBit - 1 |0;
      }
    }
  }
  if (array[start+len] !== searchedValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start - len |0;
  }
  return start + len |0;
}
Run Code Online (Sandbox Code Playgroud)

上述函数的返回值如下。

  • 如果找到该值，则返回该值的索引。
  • 如果未找到该值，则它返回-1 - nearestIndex最接近的索引是找到的索引，该索引是最接近的数字 <= 索引且上限为 0。
  • 如果数组没有在指定范围内排序，那么它将返回一些无意义的数字。

为了开始优化，让我们首先删除那个讨厌的内部 if 分支。

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+compactBS(sArr, s);

function compactBS(array, searchedValue, ARG_start, ARG_len){
  // `void 0` is shorthand for `undefined`
  var start = ARG_start === void 0 ? 0 : ARG_start |0;
  var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
  len = len - 1 | 0;
  for (let i=0x80000000; i; i >>>= 1) {
    if (len & i) {
      const noCBit = len & ~(i-1);
      // noCBits now contains all the bits in len that are
      // greater than the present value of i.
      len ^= (
        (len ^ (noCBit-1)) & 
        ((array[start+noCBit] <= searchedValue |0) - 1 >>>0)
      ); // works based on the logic that `(x^y)^x === y` is always true
    }
  }
  if (array[start+len] !== searchedValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start - len |0;
  }
  return start + len |0;
}
Run Code Online (Sandbox Code Playgroud)

现在，然后，展开它，预先计算它，使其快速、美观和良好，就像这样：

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+goodBinarySearch(sArr, s);

function goodBinarySearch(array, sValue, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = (ARG_start === void 0 ? 0 : ARG_start) | 0;
  var len = (ARG_len === void 0 ? (array.length|0) - start : ARG_len) |0;
  len = len - 1 |0;
  
  if (len & 0x80000000) {
    const nCB = len & 0x80000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40000000) {
    const nCB = len & 0xc0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20000000) {
    const nCB = len & 0xe0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10000000) {
    const nCB = len & 0xf0000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8000000) {
    const nCB = len & 0xf8000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4000000) {
    const nCB = len & 0xfc000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2000000) {
    const nCB = len & 0xfe000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1000000) {
    const nCB = len & 0xff000000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x800000) {
    const nCB = len & 0xff800000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x400000) {
    const nCB = len & 0xffc00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x200000) {
    const nCB = len & 0xffe00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x100000) {
    const nCB = len & 0xfff00000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x80000) {
    const nCB = len & 0xfff80000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40000) {
    const nCB = len & 0xfffc0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20000) {
    const nCB = len & 0xfffe0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10000) {
    const nCB = len & 0xffff0000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8000) {
    const nCB = len & 0xffff8000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4000) {
    const nCB = len & 0xffffc000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2000) {
    const nCB = len & 0xffffe000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1000) {
    const nCB = len & 0xfffff000;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x800) {
    const nCB = len & 0xfffff800;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x400) {
    const nCB = len & 0xfffffc00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x200) {
    const nCB = len & 0xfffffe00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x100) {
    const nCB = len & 0xffffff00;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x80) {
    const nCB = len & 0xffffff80;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x40) {
    const nCB = len & 0xffffffc0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x20) {
    const nCB = len & 0xffffffe0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x10) {
    const nCB = len & 0xfffffff0;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x8) {
    const nCB = len & 0xfffffff8;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x4) {
    const nCB = len & 0xfffffffc;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x2) {
    const nCB = len & 0xfffffffe;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (len & 0x1) {
    const nCB = len & 0xffffffff;
    len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
  }
  if (array[start+len|0] !== sValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start - len |0;
  }
  return start + len |0;
}
Run Code Online (Sandbox Code Playgroud)

但是等等... 分裂的耳语是更高性能的前夕。很可能，您正在紧密循环中调用二分查找。在这种情况下，我们可以预先计算将实际处理的第一个值，并使用高性能整数索引 switch 语句直接跳到它。但是，在使用它时，您必须确保在修改数组长度后永远不会重用生成的快速函数，因为这样只会搜索数组的一部分。

const clz32 = Math.clz32 || (function(log, LN2){
  return function(x) {
    return 31 - log(x >>> 0) / LN2 | 0; // the "| 0" acts like math.floor
  };
})(Math.log, Math.LN2);

const sArr = [0,4,5,6,9,13,14,21,27,44];
const compFunc = fastestBS(sArr);
for (var i=0,str="",len=sArr.length|0; i < len; i=i+1|0)
  str += sArr[i]+" is at "+compFunc(sArr[i])+"<br/>";
document.body.innerHTML = str; // show the result

function fastestBS(array, ARG_start, ARG_initLen){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start === void 0 ? 0 : ARG_start |0;
  var initLen = (ARG_initLen===void 0 ? (array.length|0)-start : ARG_initLen) |0;
  initLen = initLen - 1 |0;
  const compGoto = clz32(initLen) & 31;
  return function(sValue) {
    var len = initLen | 0;
    switch (compGoto) {
      case 0:
        if (len & 0x80000000) {
          const nCB = len & 0x80000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 1:
        if (len & 0x40000000) {
          const nCB = len & 0xc0000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 2:
        if (len & 0x20000000) {
          const nCB = len & 0xe0000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 3:
        if (len & 0x10000000) {
          const nCB = len & 0xf0000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 4:
        if (len & 0x8000000) {
          const nCB = len & 0xf8000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 5:
        if (len & 0x4000000) {
          const nCB = len & 0xfc000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 6:
        if (len & 0x2000000) {
          const nCB = len & 0xfe000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 7:
        if (len & 0x1000000) {
          const nCB = len & 0xff000000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 8:
        if (len & 0x800000) {
          const nCB = len & 0xff800000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 9:
        if (len & 0x400000) {
          const nCB = len & 0xffc00000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 10:
        if (len & 0x200000) {
          const nCB = len & 0xffe00000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 11:
        if (len & 0x100000) {
          const nCB = len & 0xfff00000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 12:
        if (len & 0x80000) {
          const nCB = len & 0xfff80000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 13:
        if (len & 0x40000) {
          const nCB = len & 0xfffc0000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 14:
        if (len & 0x20000) {
          const nCB = len & 0xfffe0000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 15:
        if (len & 0x10000) {
          const nCB = len & 0xffff0000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 16:
        if (len & 0x8000) {
          const nCB = len & 0xffff8000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 17:
        if (len & 0x4000) {
          const nCB = len & 0xffffc000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 18:
        if (len & 0x2000) {
          const nCB = len & 0xffffe000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 19:
        if (len & 0x1000) {
          const nCB = len & 0xfffff000;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 20:
        if (len & 0x800) {
          const nCB = len & 0xfffff800;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 21:
        if (len & 0x400) {
          const nCB = len & 0xfffffc00;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 22:
        if (len & 0x200) {
          const nCB = len & 0xfffffe00;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 23:
        if (len & 0x100) {
          const nCB = len & 0xffffff00;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 24:
        if (len & 0x80) {
          const nCB = len & 0xffffff80;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 25:
        if (len & 0x40) {
          const nCB = len & 0xffffffc0;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 26:
        if (len & 0x20) {
          const nCB = len & 0xffffffe0;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 27:
        if (len & 0x10) {
          const nCB = len & 0xfffffff0;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 28:
        if (len & 0x8) {
          const nCB = len & 0xfffffff8;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 29:
        if (len & 0x4) {
          const nCB = len & 0xfffffffc;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 30:
        if (len & 0x2) {
          const nCB = len & 0xfffffffe;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }
      case 31:
        if (len & 0x1) {
          const nCB = len & 0xffffffff;
          len ^= (len ^ (nCB-1)) & ((array[start+nCB|0] <= sValue |0) - 1 >>>0);
        }

    }
    if (array[start+len|0] !== sValue) {
      // remove this if-statement to return the next closest
      // element going downwards from the searched-for value
      // OR 0 if the value is less than all values in the
      // array. https://stackoverflow.com/a/44981570/5601591
      return -1 - start - len |0;
    }
    return start + len |0;
  };
}
Run Code Online (Sandbox Code Playgroud)

演示：

(function(document){"use strict";
var textarea = document.getElementById('inputbox'),
    searchinput = document.getElementById('search'),
    searchStart = document.getElementById('start'),
    searchedLength = document.getElementById('length'),
    resultbox = document.getElementById('result'),
    timeoutID = -1;
function doUpdate(){
   try {
      var txt = textarea.value.replace(/\s*\[|\]\s*/g, '').split(',');
      var arr = JSON.parse(textarea.value);
      var searchval = JSON.parse(searchinput.value);
      var textmtchs = textarea.value.match(/\s*\[|\]\s*/g);
      var start = searchStart.value || void 0;
      var sub = searchedLength.value || void 0;
      
      txt = refSort(txt, arr);
      textarea.value = textmtchs[0] +
                        txt.join(',') +
                       textmtchs[textmtchs.length-1];
      arr = JSON.parse(textarea.value);
      resultbox.value = goodBinarySearch(arr, searchval, start, sub);
   } catch(e) {
      resultbox.value = 'Error';
   }
}
textarea.oninput = searchinput.oninput = 
    searchStart.oninput = searchedLength.oninput =
    textarea.onkeyup = searchinput.onkeyup = 
    searchStart.onkeyup = searchedLength.onkeyup = 
    textarea.onchange = searchinput.onchange = 
    searchStart.onchange = searchedLength.onchange = function(e){
  clearTimeout( timeoutID );
  timeoutID = setTimeout(doUpdate, e.target === textarea ? 384 : 125);
}

function refSort(targetData, refData) {
  var indices = Object.keys(refData);
  indices.sort(function(indexA, indexB) {
    if (refData[indexA] < refData[indexB]) return -1;
    if (refData[indexA] > refData[indexB]) return 1;
    return 0;
  });
  return indices.map(function(i){ return targetData[i] })
}
function goodBinarySearch(array, sValue, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = (ARG_start === void 0 ? 0

        
    
          
          
  • 
              我只想指出，我的版本被指定为为空数组返回 `array.length`。如果你更喜欢 !pred(array[i]) &amp;&amp; pred(array[1 + i])，你可以只`return lo`，不需要额外的（昂贵的）比较。代码中的“hi + lo”项可能会溢出，这可以通过习语“lo + ((hi - lo) &gt;&gt; 1)”来避免。我认为 `if ... else` 比 `continue` + label 更具可读性；）。我的版本支持任意比较函子，它只能比较部分数据等。;) (2认同)
          
    •  
          
          
  • 
              ……这正是二分搜索比线性搜索表现更好的原因——与线性搜索相比，前者只进行对数次数的比较，如果比较代价高昂，这可能会产生很大的不同。在不改变渐近复杂性的情况下修复搜索算法中的比较使其通用性降低，因此大量数据的预期加速要小得多。 (2认同)
          
    •

Lio*_*rom 11

二分搜索 (ES6)

自下而上：

function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    if (arr[mid] === val) {
      return mid;
    }

    if (val < arr[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return -1;
}
Run Code Online (Sandbox Code Playgroud)

递归：

function binarySearch(arr, val, start = 0, end = arr.length - 1) {
  const mid = Math.floor((start + end) / 2);

  if (val === arr[mid]) {
    return mid;
  }

  if (start >= end) {
    return -1;
  }

  return val < arr[mid]
    ? binarySearch(arr, val, start, mid - 1)
    : binarySearch(arr, val, mid + 1, end);
}
Run Code Online (Sandbox Code Playgroud)

Ash*_*Jha 9

这是二进制搜索功能,你可以查看 

   function bsearch (Arr,value){
        var low  = 0 , high = Arr.length -1 ,mid ;      
        while (low <= high){
            mid = Math.floor((low+high)/2);     
            if(Arr[mid]==value) return mid ; 
            else if (Arr[mid]<value) low = mid+1;
            else high = mid-1;          
        }
        return -1 ;
    }
Run Code Online (Sandbox Code Playgroud)

Edu*_*ard 5

做得有点不同。看一看

function binarySearch(arr, n) {
  let min = 0;
  let max = arr.length - 1;
  let mid;
  while (min <= max) {
    mid = (min + max) >>> 1;
    if (arr[mid] === n) {
      return mid;
    } else if (arr[mid] < n) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }

  return -1;
}

binarySearch([1,2,3,5,56], 2);
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

60854 次

最近记录：

6 年 前
相关归档
Javascript数组:删除另一个数组中包含的所有元素 185
JavaScript中的数组与对象效率 126
<input type ="hidden">的初衷？ 100
检查用户是否安装了Chrome扩展程序 87
如何通过javascript检查是否存在查询字符串值 81
JavaScript - 使用数组填充下拉列表 55
JavaScript中的"IsNullOrWhitespace"？ 54
动态设置iframe src 54
nodejs加载文件 51
谷歌浏览器 - JavaScript版本 46
难疑归档
停止EditText在Activity启动时获得焦点 2770
如何在JavaScript中获取查询字符串值？ 2701
Git获取远程分支 2088
如何分析在Linux上运行的C++代码？ 1732
C#在foreach中重用变量是否有原因？ 1631
将文件从Docker容器复制到主机 1438
"无法找到或加载主类"是什么意思？ 1277
const int*,const int*const和int const*之间有什么区别？ 1262
你怎么能加速Eclipse？ 1258
在Python中创建多行注释的方法？ 1081
Copyright Info

© Copyright 2013-2021 admin@qa.1r1g.com

如未特别说明，本网站的内容使用如下协议:
Creative Commons Atution-NonCommercial-ShareAlike 4.0 International license.

用以下方式浏览
参考资料
回到顶部
网安备44200002443738
粤ICP备19038133号