1、什么是数组

数组是存储在连续内存位置的项目的集合，将多个相同类型的项目（有些语言中也可以是不同类型，比如 JavaScript）存储在一起。这使得通过简单地向基值添加偏移量来计算每个元素的位置变得更加容易，即，数组的第一个元素的内存位置（通常由数组的名称表示）。基值是索引 0，两个索引之间的差值是偏移量。每个元素都可以通过它们在数组中的索引来唯一标识。

简单来说数组就是用于储存多个相同类型数据的集合。（当然，js中的数组也可以存储不同类型数据，但是！不建议这样做！）如下图：

1.1 数组的应用

数组存储相同数据类型（有些语言中也可以是不同类型，如JavaScript）的数据元素。
当数据集的大小已知时，使用数组。
用于解决矩阵问题。
在计算机中用作搜索表。
数据库记录也是由数组实现的。
帮助实现排序算法。
同一类型的不同变量可以保存在一个名称下。
数组可用于 CPU 调度。
用于实现其他数据结构，如栈、队列、堆、哈希表等。

1.2 数组的优缺点

数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据（JS里可以是任意类型）。

关键点：连续的存储空间（数组可以进行随机访问）

在操作系统中数组的特性为

存储在物理空间上是连续的。
底层的数组长度是不可变的（js中之所以能随意修改数组的长度，是因为js做了数据优化）
数据的变量，指向了数组第一个元素的位置

底层数组长度不可变，那底层是如何添加与删除的：假设当前的数组的长度为8，此时需要网数组中添加一个新数据，底层会新建一个16位长度的数组，将之前的长度为8的数组中的数据拷贝过来，然后将新数据添加进该数组。当为删除时，假设此时删除数组索引为5的数据，那么索引为5之后的数据到最后一位数据会往前挪，因为存储在物理空间上是连续的。

优缺点

优点：

查询性能好，指定查询某一个位置
易于创建和使用
复杂数据结构的基础构建块

缺点：

因为空间必须是连续的，所以如果数据比较大，当系统的空间碎片较多的时候，容易存不下。（空间碎片：何为空间碎片，当数组中出现空值，导致数组不是连续的，这个空值为空间碎片，如果系统没有清除掉，那么新数据就存不下，举个例子，一个数据组的长度为10，之中有三个不连续的空值，当存入三个新数据，此时会存不进去，因为此时系统中已经存入数组的长度为10，包括啦空值，系统整理空间碎片会很慢，大概是这，需要操作系统原理）
因为数组的长度是固定的，所以数组的内容难以被添加和删除，导致昂贵的插入/删除或重排

1.3 数组的操作

关于 JavaScript 和 Go 中数组（Go中还有切片）的一些方法，为了节省篇幅，这里就不赘述了，可看下面的推荐文章：

JavaScript 数组相关操作

Go 数组（切片）相关操作

2、线性搜索

2.1 经典线性搜索

顺序搜索：按一定的顺序遍历数组并检查每个元素，比较典型的就是线性搜索。

什么是线性搜索？假设该项目以随机顺序存在于数组中，我们必须找到一个项目。那么搜索目标项目的唯一方法就是首先从第一个位置开始并将其与目标进行比较。如果项目在同一位置，我们将返回当前项目的位置。否则，我们将移动到下一个位置。如果我们到达数组的最后一个位置仍然找不到目标，我们返回-1。这称为线性搜索或顺序搜索。如下图：

JavaScript 实现：

function linearSearch(arr, ele) {
  for(let i = 0; i < arr.length; i++){
    if(arr[i] === ele) {
      return i;
    }
  }
  return -1;
}
const arr = [3, 7, 1, 4, 9, 2];
const elementToFind = 4;
console.log(`element found at index: ${linearSearch(arr, elementToFind)}`); 
// element found at index: 3

时间复杂度： O(N)
辅助空间： O(1)

Go 实现：

func linearSearch(arr []int, ele int) int {
  for i := 0; i < len(arr); i++ {
    if arr[i] == ele {
      return i
    }
  }
  return -1
}
arr := []int{3, 7, 1, 4, 9, 2}
ele := 4
fmt.Printf("element found at index: %d", linearSearch(arr, ele))
// element found at index: 3

2.2 哨兵线性搜索

顾名思义，哨兵线性搜索（Sentinel Linear Search）是一种线性搜索，与传统的线性搜索相比，它的比较次数有所减少。

在这个搜索中，数组的最后一个元素被替换成要搜索的元素，然后在数组上进行线性搜索，而不检查当前的索引是否在数组的索引范围内，因为要搜索的元素肯定会在数组中找到，即使它不在原数组中，因为最后一个元素被替换成了它。所以，要检查的索引永远不会超出数组的范围。在最坏的情况下，比较的次数将是(N + 2)（在最坏情况下，因为要对目标元素与数组末尾位置元素进行判断，因此需要再进行两次判断，多出 2 次比较）。

尽管在最坏情况下，两种算法的时间复杂度都是O(n)。只是在哨兵线性搜索中的比较次数要比线性搜索少。

基本思路：哨兵线性搜索的基本思想是在数组的末端增加一个额外的元素（即哨兵值），该元素与搜索键相匹配。通过这样做，我们可以避免在循环中对数组末端的条件进行检查，一旦找到哨兵元素，就提前终止搜索。这样就不需要对数组的末端进行单独检查，从而使算法的平均性能略有提高。

哨兵线性搜索算法的好处：它消除了对数组末端的单独检查，这可以提高算法的平均情况性能。然而，它并没有改善最坏情况下的性能，它仍然是O(n)（其中n是数组的大小），因为我们可能需要扫描整个数组来找到哨兵值。

JavaScript 实现：

function sentinelLinearSearch(arr, target) {
  const n = arr.length
  const lastElement = arr[n - 1] // 记录最后一个元素
  arr[n - 1] = target // 将目标值替换成最后一个元素，从而省略了边界判断
  let i = 0
  while (arr[i] !== target) {
    i++
  }
  // 恢复原数组
  arr[n - 1] = lastElement
  // 区分搜索成功和失败的情况
  if (i < n - 1 || arr[n - 1] === target) {
    return i
  } 
  return -1
}
// 测试
const arr = [2, 4, 7, 9, 12, 23, 34, 45, 56, 67]
console.log(sentinelLinearSearch(arr, 7)) // output: 2
console.log(sentinelLinearSearch(arr, 10)) // output: -1

时间复杂度： O(N)
辅助空间： O(1)

Go 实现：

func SentinelLinearSearch(arr []int, target int) int {
    n := len(arr)
    last := arr[n - 1] // 记录最后一个元素
    arr[n - 1] = target // 将目标值替换成最后一个元素，从而省略了边界判断
    i := 0
    for arr[i] != target {
        i++
    }
    arr[n - 1] = last // 恢复原数组
    if i < n - 1 || arr[n - 1] == target { // 区分搜索成功和失败的情况
        return i
    }
    return -1
}

3、二分搜索

区间搜索：专门为在 已排序的数据结构 中搜索元素而设计的，通常区间搜索会比线性搜索更有效，因为它们反复以搜索结构的中心为目标，并将搜索空间分成两半。比较典型的就是二分搜索。

3.1 经典二分搜索

3.1.1 迭代实现

JavaScript实现：

function binarySearch(arr, ele) {
  let left = 0;
  let right = arr.length - 1;
  while(left <= right){
    const mid = Math.floor(left + (right - left) / 2);
    if(ele === arr[mid]) {
      return mid;
    } else if(ele < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return -1;
}
const arr = [1, 2, 3, 4, 7, 9];
const elementToFind = 4;
console.log(`element found at index: ${binarySearch(arr, elementToFind)}`);
// element found at index: 3

Go 实现

func binarySearch(arr []int, ele int) int {
  left := 0
  right := len(arr) - 1
  for left <= right{
    mid := left + (right - left) / 2
    if ele == arr[mid] {
      return mid
    } else if ele < arr[mid] {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return -1
}
arr := []int{1, 2, 3, 4, 7, 9}
ele := 4
fmt.Printf("element found at index: %d", binarySearch(arr, ele))
// element found at index: 3

注意： 这里我们计算中值的写法：

const mid = Math.floor(left + (right - left) / 2);

为什么我们要这样计算中间指数？可以简单地将较低和较高的指数相加并除以 2 吗？比如

const mid = (left + right) / 2;

还真不一定行，如果 left + right 的总和大于最大正整型值 (2312^{31}231 – 1)，就会出现溢出了。

高能预警：这也是各个大厂算法中考试的一个隐藏点，有些面试官可能会因为你没考虑溢出的情况而把你 pass 掉！~

3.1.2 递归实现

大致的实现思路是：

在函数执行开始时，会先判断当前搜索范围是否有效（即左侧下标是否大于右侧下标），如果无效，则退出递归，并返回-1，表示未找到目标元素。
如果当前搜索范围有效，函数会计算当前搜索范围的中间元素下标，并将其与目标值进行比较。
如果当前中间元素正好等于目标值，则直接返回该元素的下标；
如果当前中间元素小于目标值，则代表目标值可能在数组的右侧区域中，因此将搜索范围右移一位，递归调用二分搜索的函数进行下一轮搜索；
如果当前中间元素大于目标值，则代表目标值可能在数组的左侧区域中，因此将搜索范围左移一位，递归调用二分搜索的函数进行下一轮搜索。

JavaScript 实现：

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 确定搜索范围无效，退出递归，该分支未找到目标元素
  if (left > right) {
    return -1;
  }
  // 计算中间元素下标
  const mid = Math.floor(left + (right - left) / 2);
  if (arr[mid] === target) {  
    // 当前中间元素正好等于目标值
    return mid;
  } else if (arr[mid] < target) {  
    // 中间元素小于目标值，在右侧区域中继续搜索
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {  
    // 中间元素大于目标值，在左侧区域中继搜索
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

二分搜索的递归实现：通过不断缩小搜索范围来确定目标元素的位置。函数接受4个参数：

第一个参数为已排序的数组

第二个参数为要搜索的目标元素

第三和第四个参数表示当前搜索范围在数组中的左右下标。

Go 实现：

func binarySearch(arr []int, low int, high int, target int) int {
    // high < low 表示整个数组都被搜索，但是没有找到目标元素
    if high < low {
        return -1
    }
    // 用 int((low + high) / 2) 可能会导致最大值 + 最小值溢出
    mid := low + ((high - low) >> 1)
    if arr[mid] > target {
        // 当中间元素的值比target大时，在数组左侧进行搜索
        return binarySearch(arr, low, mid - 1, target)
    } else if arr[mid] < target {
        // 当中间元素的值比target小时，在数组右侧进行搜索
        return binarySearch(arr, mid + 1, high, target)
    } else {
        // 找到了目标元素，返回其索引
        return mid
    }
}

参数：

low：当前搜索区间的最低点索引
high：当前搜索区间的最高点索引
target：需要搜索的目标值

函数首先判断是否找到目标元素或者整个数组都已被搜索过。如果未找到，则找出当前搜索区间的中心元素的索引（由于low + high可能非常大，因此使用移位操作代替简单的平均除法）。中心元素的值用来与目标值进行比较。当中心元素比目标值大时，向前半部分继续搜索；当中心元素比目标值小时，向后半部分继续搜索；如果中心元素正好等于目标值，则已找到该元素。每次递归时，都会将搜索区域一分为二并递归搜索目标元素的对应半部分，最终在左侧或右侧子数组中找到目标值。

【数据结构与算法】数组常见搜索算法的 JavaScript 和 Go 实现~（上）

1、什么是数组

1.1 数组的应用

1.2 数组的优缺点

1.3 数组的操作

2、线性搜索

2.1 经典线性搜索

2.2 哨兵线性搜索

3、二分搜索

3.1 经典二分搜索

3.1.1 迭代实现

3.1.2 递归实现

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【数据结构与算法】数组常见搜索算法的 JavaScript 和 Go 实现~（上）

1、什么是数组

1.1 数组的应用

1.2 数组的优缺点

1.3 数组的操作

2、线性搜索

2.1 经典线性搜索

2.2 哨兵线性搜索

3、二分搜索

3.1 经典二分搜索

3.1.1 迭代实现

3.1.2 递归实现

热门文章

最新文章

相关课程

相关电子书