算法：线性搜索和二分搜索-js教程-PHP中文网

算法：线性搜索和二分搜索

心靈之曲

发布： 2024-12-06 08:21:31

转载

630人浏览过

算法：线性搜索和二分搜索

有一些简单的算法引入了逻辑和数据结构的基本概念，而其他算法则旨在提高复杂性。

搜索算法对于在大量数据中查找信息非常有用，例如在电话簿或计算机上的文件中查找联系人。

从这个意义上说，本文旨在介绍涉及线性搜索和二分搜索算法的概念。

1。线性搜索

顺序扫描列表以查找元素
一个例子是在数组中搜索特定数字

线性搜索算法，在叙述性陈述中，意味着有一个整数数组和一个将作为搜索参考的值，称为目标，它将作为输入参数。从这个意义上说，有一个函数接收这些值，首先它遍历该数组的每个位置，直到现有位置的最大大小，主要使用 for 来实现，然后使用 if，它条件是检查：每个位置的值是否等于目标。如果找到该值，该函数将返回该位置的索引，或者返回 -1，表示未找到情况。

使用 javascript 的示例是：

function linearsearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

登录后复制

因此，这个算法的目的是返回元素所在的位置，或者说索引，甚至，只是简单地定位到第一个对应的元素，而不需要找到后继续。这种行为是由于算法的指令而发生的，当条件满足时，执行带有元素索引的返回，然后退出循环，结束函数。

该算法在列表较小或无序列表的场景中非常有用。每个元素都可以需要遍历，并且没有额外的内存占用。

2。二分查找

二分搜索算法是一种更有效的算法形式，可以在排序数组中查找给定值。这是通过重复地将搜索范围一分为二来实现的，这使得它比大型数据集的线性搜索要快得多。二分查找的复杂度为 o(log n)，而线性查找的复杂度为 o(n)。

作为 javascript 中的示例，我们有：

function binarySearch(array, target) {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    const middle = Math.floor((low + high) / 2);

    if (array[middle] < target) {
      low = middle + 1;
    } else if (array[middle] > target) {
      high = middle - 1;
    } else {
      return middle;
    }
  }
  return -1;
}

登录后复制

逻辑由两个指针开始，一个位于数组的开头（低位），另一个位于数组的末尾（高位）。因此，计算中间索引 const middle = math.floor((low high) / 2)。这样，每一步都会将中间元素与目标进行比较：如果中间元素等于目标，则返回索引。但是，如果中间元素小于目标，或者中间目标，大于目标的数字将被丢弃，将最终索引调整为 high = middle - 1。重复此过程，直到找到目标或范围变得无效（在本例中为 low） > 高。

在查找有序数据（例如在字母字典或一组有序日期中）时，二分搜索非常有效。它们往往更快、更高效，因为每次迭代中问题都可以分为更小的子问题。

因此，可以理解线性搜索很简单并且适用于小型列表。二分查找效率更高，但需要有序数据。

了解不同算法的工作原理及其使用环境是构建高效计算解决方案的重要一步。尝试实施和分析这些方法，并发现如何调整这些策略来解决现实世界的挑战。 =)

以上就是算法：线性搜索和二分搜索的详细内容，更多请关注php中文网其它相关文章！