背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读四个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》。

当前阅读周书籍：《数据结构与算法JavaScript描述》。

检索算法

顺序查找

对于查找数据来说，最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断，直到找到了想要的结果，或者直到列表结尾也没有找到。这种方法称为顺序查找，有时也被称为线性查找。它属于暴力查找技巧的一种，在执行查找时可能会访问到数据结构里的所有元素。

顺序查找的实现很简单。只要从列表的第一个元素开始循环，然后逐个与要查找的数据进行比较。如果匹配到了，则结束查找。如果到了列表的结尾也没有匹配到，那么这个数据就不存在于这个列表中。

seqSearch()函数：

function seqSearch(arr, data) {
  for (var i = 0; i < arr.length; ++i) {
    if (arr[i] == data) {
      return true;
    }
  }
  return false;
}

如果在数组中找到了参数data，函数会立即返回true。如果直到数组的结尾也没有找到该参数，函数将会返回false。

从1到100的区间生成的随机数来填充一个数组。同时使用一个函数输出这个数组的内容：

function dispArr(arr) {
  for (var i = 0; i < arr.length; ++i) {
    putstr(arr[i] + ' ');
    if (i % 10 == 9) {
      putstr('\n');
    }
  }
  if (i % 10 != 0) {
    putstr('\n');
  }
}

var nums = [];
for (var i = 0; i < 100; ++i) {
  nums[i] = Math.floor(Math.random() * 101);
}
dispArr(nums);
putstr('输入一个要查找的数字：');
var num = parseInt(readline());
console.log();
if (seqSearch(nums, num)) {
  console.log(num + ' 出现在这个数组中。');
} else {
  console.log(num + ' 没有出现在这个数组中。');
}
console.log();
dispArr(nums);

该程序创建了一个包含0～100随机数的数组。用户输入一个值，然后被程序查找，并且输出查找的结果。最后，该程序会输出整个数组的内容用于判断函数的返回值是否正确。示例如下：

输入一个要查找的数字：23

23 有出现在这个数组中。
13 95 72 100 94 90 29 0 66 2 29
42 20 69 50 49 100 34 71 4 26
85 25 5 45 67 16 73 64 58 53
66 73 46 55 64 4 84 62 45 99
77 62 47 52 96 16 97 79 55 94
88 54 60 40 87 81 56 22 30 91
99 90 23 18 33 100 63 62 46 6
10 5 25 48 9 8 95 33 82 32
56 23 47 36 88 84 33 4 73 99
60 23 63 86 51 87 63 54 62

查找最小值和最大值

在已排序的数据结构中查找这两个值是个很简单的事情。然而，在未排序的数据结构中要找到这两个值则更具挑战。

首先看看如何在数组中查找最小值，算法如下。

1. 将数组第一个元素赋值给一个变量，把这个变量作为最小值。
2. 开始遍历数组，从第二个元素开始依次同当前最小值进行比较。
3. 如果当前元素数值小于当前最小值，则将当前元素设为新的最小值。
4. 移动到下一个元素，并且重复步骤3。
5. 当程序结束时，这个变量中存储的就是最小值。

findMin()函数：

function findMin(arr) {
  var min = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

需要注意的关键部分，由于我们假设数组的第一个元素就是当前的最小值，所以这个函数会从数组的第二个元素开始进行处理。

查找数组中的最小值：

var nums = [];
for (var i = 0; i < 100; ++i) {
  nums[i] = Math.floor(Math.random() * 101);
}
var minValue = findMin(nums);
dispArr(nums);
console.log();
console.log('最小值是：' + minValue);

以上程序的输出结果如下：

89 30 25 32 72 70 51 42 25 24 53
55 78 50 13 40 48 32 26 2 14
33 45 72 56 44 21 88 27 68 15
93 98 73 28 16 46 87 28 65 38
67 16 85 63 23 69 64 91 9 70
81 27 97 82 6 88 3 7 46 13
11 64 31 26 38 28 13 17 69 90
1 6 7 64 43 9 73 80 98 46
27 22 87 49 83 6 39 42 51 54
84 34 53 78 40 14 5 76 62
最小值是：1

查找最大值算法的思路与此类似，先将数组的第一个元素设为最大值，然后循环对数组剩下的每个元素与当前最大值进行比较。如果当前元素的值大于当前的最大值，则将该元素的值赋值给最大值变量。

findMax()函数：

function findMax(arr) {
  var max = arr[0];
  for (var i = 1; i < arr.length; ++i) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

使用findMax()函数：

var nums = [];
for (var i = 0; i < 100; ++i) {
  nums[i] = Math.floor(Math.random() * 101);
}
var minValue = findMin(nums);
dispArr(nums);
console.log();
console.log();
console.log('最小值是：' + minValue);
var maxValue = findMax(nums);
console.log();
console.log('最大值是：' + maxValue);

以上程序的输出结果如下：

26 94 40 40 80 85 74 6 6 87 56
91 86 21 79 72 77 71 99 45 5
5 35 49 38 10 97 39 14 62 91
42 7 31 94 38 28 6 76 78 94
30 47 74 20 98 5 68 33 32 29
93 18 67 8 57 85 66 49 54 28
17 42 75 67 59 69 6 35 86 45
62 82 48 85 30 87 99 46 51 47
71 72 36 54 77 19 11 52 81 52
41 16 70 55 97 88 92 2 77

最小值是：2

最大值是：99

二分查找算法

二分查找算法比顺序查找算法更高效。

要理解二分查找算法的原理，可以想象一下你在玩一个猜数字游戏，这个数字位于1～100之间，而要猜的数字是由你的朋友来选定的。

游戏规则是，你每猜一个数字，你的朋友将会做出以下三种回应中的一种：

1. 猜对了；
2. 猜大了；
3. 猜小了。

根据以上规则，第一次猜50将会是最佳策略。如果猜的值太大，就猜25。如果太小，就应该猜75。每一次猜测，都应该选择当前最小值和最大值的中间点（取决于你上次猜测的结果是太大还是太小）。然后将这个中间值作为下次要猜的数字。只要你采用这个策略，就可以用最少的次数猜出这个数字。

这个算法只对有序的数据集有效。算法描述如下：

1. 将数组的第一个位置设置为下边界（0）。
2. 将数组最后一个元素所在的位置设置为上边界（数组的长度减1）。
3. 若下边界等于或小于上边界，则做如下操作：

a．将中点设置为（上边界加上下边界）除以2。
b．如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加1。
c．如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减1。
d．否则中点元素即为要查找的数据，可以进行返回。

使用二分查找算法：

function binSearch(arr, data) {
  var upperBound = arr.length - 1;
  var lowerBound = 0;
  while (lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound) / 2);
    if (arr[mid] < data) {
      lowerBound = mid + 1;
    } else if (arr[mid] > data) {
      upperBound = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

var nums = [];
for (var i = 0; i < 100; ++i) {
  nums[i] = Math.floor(Math.random() * 101);
}
insertionsort(nums);
dispArr(nums);
console.log();
putstr('输入一个要查找的值：');
var val = parseInt(readline());
var retVal = binSearch(nums, val);
if (retVal >= 0) {
  console.log('已找到 ' + val + ' ，所在位置为：' + retVal);
} else {
  console.log(val + ' 没有出现在这个数组中。');
}

以上程序运行的输出结果为：

0 1 2 3 5 7 7 8 8 9 10
11 11 13 13 13 14 14 14 15 15
18 18 19 19 19 19 20 20 20 21
22 22 22 23 23 24 25 26 26 29
31 31 33 37 37 37 38 38 43 44
44 45 48 48 49 51 52 53 53 58
59 60 61 61 62 63 64 65 68 69
70 72 72 74 75 77 77 79 79 79
83 83 84 84 86 86 86 91 92 93
93 93 94 95 96 96 97 98 100
输入一个要查找的值：37
已找到37，所在位置为：45

总结

在列表中查找数据有两种方式：顺序查找和二分查找。

顺序查找适用于元素随机排列的列表；二分查找适用于元素已排序的列表。

二分查找效率更高，但是你必须在进行查找之前花费额外的时间将列表中的元素排序。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。