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

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

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

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

**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; 
}

所以该算法的目的是返回元素所在的位置，或者说索引，甚至只是定位第一个对应的元素，而不需要找到之后再继续。这种行为是由于算法的指令而发生的，当其条件满足时，使用元素的索引执行“return”，然后退出循环，结束该函数。

该算法在列表较小或无序列表的情况下很有用。每个元素都可能需要遍历，并且没有额外的内存占用。

**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)”。这会在每一步将中间元素与目标进行比较：如果中间元素与目标匹配，则返回索引。但是，如果中间元素小于目标，即“中间 < 目标”，则意味着丢弃较小的数字，将开头放置为“低 = 中间 + 1”。如果中间元素又大于目标“middle > target”，则大于目标的数字将被丢弃，将最终索引调整为“high = middle - 1”。该过程重复进行，直到找到目标或范围变得无效（在“低 > 高”的情况下）。

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

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

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

CLIS.CC

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