如何在 javascript 中只有两种类型的项目 0、1 的数组中最有效地查找项目的索引

How to most efficently find the index of an item in an array with only two types of items 0, 1 in javascript

本文关键字：项目 数组 有效地 索引 查找 javascript 类型 两种      更新时间：2023-09-26

例如你有

var arr = [0,0,0,1,0,1,1,0,0,0,1];

并且您想参考前 1 找到第一个 0 的位置。 arr.indexOf会直接解决问题，但我不确定它是否线性比较数组中的每个项目？二叉搜索是行不通的，因为如果你排序然后查找元素，你会丢失索引......任何其他方法都可以到达第一个 1 并说啊哈！索引 3，一次不去一个元素？

它从数组的开头迭代搜索。

规范的相关部分：

重复，同时k < len

  • 让 k Present 是调用带有参数ToString(k)的O的[[HasProperty]]内部方法的结果。
  • 如果k现在是真的，那么
    • 让elementK是调用O的[[Get]]内部方法的结果，参数为ToString(k)。
    • 让我们同样是将严格相等比较算法应用于searchElement和elementK的结果。
    • 如果相同，则返回k 。
  • 将k增加 1。

来源： http://es5.github.io/#x15.4.4.14

是的，一旦对数组结构没有保证 - 没有什么比线性搜索更有效的了。

我不确定如何为没有某些东西提供正式证明。

我有一个有效的方法。

您拥有的实例

var arr = [0,0,0,1,0,1,1,0,0,0,1];

然后你创建一个新的数组 sum = {sum[i] = ∑（arr[j]，j<=i）}

var sum = [0,0,0,1,1,2,3,3,3,3,4];

所以，你可以使用二叉搜索来找到第一个总和[j]==1

但是如果我们更新 arr 的元素，我们将再次用 O（n） 计算总和

有一些数据结构，如段树（https://en.wikipedia.org/wiki/Segment_tree）和二叉索引树（BIT https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/）可以解决这个问题，它允许使用O（logn）查询和更新范围的总和

因此，您可以使用O（logn）*O（logn）解决此问题

您可以迭代遍历数组，但一旦找到第一个 1，就会停止。例如，可以使用以下代码：

boolean found = false;
int arr = {0,0,0,1,0,1,1,0,0,0,1};
for (int i = 0; found != true && i <arr.length; i++){
    if(arr[i] == '1'){
    found = true;
    }
相关文章：