代码之家 › 专栏 › 技术社区 › Max Koretskyi

排序数组中以2代替1递增的线性搜索

sorting algorithm arrays javascript

Max Koretskyi · 技术社区 · 7 年前

我有一个任务来实现 contains 作用 使用线性搜索 这适用于排序数组。我是这样做的:

function contains(a, e) {
  for (let i = 0; i < a.length; i++) {   
    if (e === a[i]) {
      return true;
    } else if (e < a[i]) {
      return false;
    }
  }
  return false;
}

我们可以通过更快地增加索引来进一步改进速率(例如,2)。这将减少在排序列表中搜索。

我不明白我们怎么做,因为我们不能跳过元素。唯一想到的是检查当前索引和以前的索引:

if (e === a[i] || e === a[i-1]) {

该示例使用JavaScript语言。然而,我感兴趣的是不特定于任何语言的通用解决方案,因此可以将其视为伪代码。

3 回复 | 直到 7 年前

kfx 7 年前

如前所述,我将添加我自己的答案,其中包含与前面两个答案相同的想法。

假设问题是找到 key array i 从…起 0 到 array.length-1 . 通常情况下,人们会通过评估 array[i] == key 对于每个 一、 诀窍是评估 array[i] < key 数组[i]==键 . 如果这个条件为false,那么它认为如果键在数组中,则它要么在位置上 array[i-1] 或 array[i]

下面提供了一个可运行且经过测试的代码。

function contains(array, key) {
  var i;
  for (i = 0; i < array.length; i += 2) {   
    if (array[i] < key) {
      // continue search
      continue;
    }
    // compare with the current element
    if (array[i] === key) {
      return true;
    }
    // compare with the skipped element
    if (i > 0 && array[i - 1] === key) {
      return true;
    }
    // it's neither the current nor the skipped element
    return false;
  }
  // for even-sized arrays, check the last element
  if (i < array.length + 1) {
    if (array[i - 1] === key) {
      return true;
    }
  }
  return false;
}

console.log(contains([10, 20, 30, 40], 10)); // true
console.log(contains([10, 20, 30, 40], 20)); // true
console.log(contains([10, 20, 30, 40], 30)); // true
console.log(contains([10, 20, 30, 40], 40)); // true
console.log(contains([10, 20, 30, 40], 25)); // false

同样,这个想法可以推广到跳过二、三。。。 n n-1 应将相等性的显式检查添加到循环的bpdy中。不过,对于足够大的数组,二进制搜索总是会更好,就像二进制搜索一样 O(n) 比较:跳过某些元素可以通过常数因子提高性能,但不是渐进的。

Dinesh Kumar 7 年前

function contains(a, e) {
  for (let i = 0; i < a.length; i+= 2) {   
    if (e === a[i]) {
      return true;
    } else if (e < a[i]) 
    {
      //now compare with skipped element
       if(e == a[i-1]) return true; 
       else return false;
    }
  }
  return false;
}

Félix Adriyel Gagnon-Grenier 7 年前

如果数组包含数字,如果不检查元素是否相等,但检查搜索的元素是否大于当前索引中的元素,则可以跳过每一秒的元素。

在你检查的每个循环中 if array[i] < a a 你继续,否则你在 i-1 i-1 .

Array: [1, 2, 4, 5, 7, 10]
a: 5

array[0] < 5 -> true
array[2] < 5 -> true
array[4] < 5 -> false

此时,您知道如果您的值存在于数组中,则它位于数组[2]和数组[4]之间,因为我们知道 array[2] < 5 < array[4]

array[3] == 5

如果返回true,则数组包含该值,否则不包含该值

function contains2(a, e) {
  for (let i = 0; i < a.length; i += 2) {
    if (a[i] < e) {
      continue;
    } else {
      if (a[i-1] === e) {
        return true;
     } else if (a[i] === e) {
       return true;
     } else {
       return false;
     }
    }
  }
  return false;
}

这就是实现。在下面链接的JSBin中,您可以看到这两个函数的比较。我添加了一个日志来计算每个循环运行的频率。在给定的示例中,您的函数需要运行8次,因为它将搜索值与值进行比较 array[0], array[1], array[2], array[3], array[4], array[5], array[6], array[7] 直到给出结果。 array[0], array[2], array[4], array[6], array[8] array[7] . 这就是为什么它需要更少的比较。

https://jsbin.com/vojahoyaju/edit?js,console