append 降低数组位数_4.有序数组

果然我在这个专栏的更新上没有压力，哈哈，这挺好的，不用在乎别人是不是看，反正自己总结出来，巩固了知识就好。

有序数组其实就是数组的进化版，和数组唯一的区别就是“有序”这两个字，就是指在这个数组当中的所有数据，必须按照一定的顺序来排列，即便是插入新数据或者删除原有数据，仍然要按照既定规则来排序；而普通的数组是不考虑顺序的，新添加的数据可以在末尾（JavaScript：Array.push；Python：list.append）也可以在开头（JavaScript：Array.unshift；Python：list.insert(0, element)），当然这里不考虑语言的差异，括号里面仅仅是两种常见语言的样例。

1 插入

比如有一个数组 [3, 17, 80, 202]，它如果是个普通数组，当我们想插入新的数值 75 时，可以直接放在数组最后：

那么，这里只需要 1 步就能完成操作了。

可如果是个有序数组，并且按照数字升序排列，就必须要找到一个合适的位置来插入新的数值，从而使得整个数组依旧保持有序：

那么这个步骤就不可能只需 1 步完成了，计算机需要先找到合适的位置，然后还需要把应该属于其后面的值后移，给插入腾出位置，最后再插入 75。

（1）检查索引 0 的值，并对比其是否大于 75：

（2）因为 3 小于 75，按照升序的规则，75 应该在它后面的位置，所以再检查下一个索引 1 的值：

（3）因为 17 小于 75，继续检查下一个索引：

（4）这次的 80 明显大于 75，所以可以确定把 75 放置在索引 2 这个位置，并把之后的所有值后移即可，首先后移最后一个值：

（5）接着后移 80：

（6）终于可以把 75 插入到正确的位置上了：

如上所述，我们可以看到，如果在有序数组当中插入新值，首先就要遍历以此确定需要插入的位置，这也就比普通数组多了很多步骤，意味着在插入数据方面，其性能比不上普通的数组；但是有序数组在查找方面，有其特殊的优势。

2 查找

普通的数组查找其实就是标准的遍历比较，从头至尾逐个检查，直到获取到了完全一致（或者根据正则表达式得到相对一致）的结果，这种方式被称为线性查找。

比如这里有个数组 [3, 17, 75, 80, 202]，如果我们想要查找 22 是否存在，是普通数组的话，就需要逐个元素检查对比，直到确定不存在；而有序数组则不必遍历整个数组，只要查找到 75 就可以停止了，因为 75 > 22，而后面的元素一定比 75 大，所以 22 并不存在。

这里可以用 JavaScript 来尝试实现一个有序数组的线性查找（用的是比较基础的方式，没什么骚操作）：

// 定义一个函数 linearSearch
function linearSearch(array, value) {// 遍历数组的每一个元素for (let i = 0; i < array.length; i++) {// 如果该元素等于我们要寻找的值，则记录在控制台，并退出循环if (array[i] === value) {console.log(`Found at index ${i}!`);break;// 如果该元素大于要寻找的值，则退出循环} else if (array[i] > value) {console.log('Not found!');break;}}
}

所以，在大多数情况下，有序数组的线性查找都要快于普通数组，除非要找的值大于等于最后一个，那就没什么区别了。

到这里，其实我们仍然看不出有序数组比普通数组的优势有多大，这是因为我们一直在使用线性查找，当然这仅仅是查找算法当中的一种，而且是最基础的一种；而改变算法，我们就可以看出巨大的不同了，比如二分查找。

3 二分查找

其实二分查找的原理很简单，就是我们经常玩的那种猜数字的游戏，从 1 到 100 的数字当中，出题人确定了一个，其他人则猜测，出题人可以根据猜测结果说数字猜大了还是小了；大多数人都会先猜 50，而不是 1 ——因为不管接下来是更大还是更小，我们能可以排除掉一半的错误答案，大幅度的降低下一轮猜测的范围。

这里有个小范例，为了偷懒，我们就以数字 1 到 10 为例：

其实这就是二分查找的通俗描述，我也不用像其他算法书上面写一堆概念什么的了，哈哈；从这里可以看出来，普通数组因为没有排序，所以不可能使用二分查找，也就是说，有序数组有这个优势。

我们可以假设有包含 9 个元素的有序数组，计算机目前还不知道每个索引的值：

然后我们尝试用二分法来查找 7 这个值：

（1）首先检查正中间的索引 4，因为数组长度已知，所以将长度除以2就可以精确的判断正中间的内存地址，然后检查了：

这里的值是 9，大于 7，所以可以推测出 7应该在其之前的索引当中，我们也同时排除了从 9 开始的后面的索引地址：

（2）检查 9 前面的格子，同样从中间开始，由于是复数所以索引 1 或者 2 都可以，这里随机挑选了索引 1：

这里值是 4，同理可以排除 4 以及之前的值了：

（3）剩下两个索引，随机选择索引 2：

（4）只剩下一个了，再检查（如果还没有，就说明整个有序数组中不存在该值）：

这样我们找到了 7，共使用了 4 步；虽然在这个特例当中使用线性查找也是 4 步（因为 7 在索引 3 的位置上），但是如果是在 100 个值当中查找呢？我们后面可以看看二分查找的优势。

下面是二分查找的 JavaScript 实现：

function binarySearch(array, value) {// 首先设置上下界，以索引 0 为下界，最后一个索引为上界let lowerBound = 0;let upperBound = array.length - 1;// 循环检查上下界之间的最中间元素while (lowerBound <= upperBound) {// 找出最中间的索引，并使用 Math.floor 函数向下转化为整数let midpoint = Math.floor((upperBound + lowerBound) / 2);// 获取最中间索引的值valueOfMidpoint = array[midpoint];// 如果等于 value，搞定收工// 否则就需要根据该值大于还是小于查找值，来调整上下界if (value < valueOfMidpoint) {upperBound = midpoint - 1;} else if (value > valueOfMidpoint) {lowerBound = midpoint + 1;} else if (value === valueOfMidpoint) {return midpoint;break;}}
}

4 二分查找和线性查找的比较

上面提及的 100 个值的有序数组，两种查找算法的最多步数如下：

• 线性查找：100步；如果要找的值大于等于最后一个值，就必需100步
• 二分查找：7步；因为每次猜测后会排除掉一半的元素，所以我们最大步数就是：
  • 第一步，剩50
  • 第二步，剩25
  • 第三步，剩13
  • 第四步，剩7
  • 第五步，剩3
  • 第六步，剩1
  • 第七步，确定

换个角度我们可以发现一个规律，每次有序数组长度乘以 2，二分查找所需的最多步数只会加 1，这就很能体现二分查找的优势了，两者的复杂度对比如下图：

如果数组变得更大，比如说有 10,000 个元素，线性查找最多要 10,000 步，而二分查找最多只需要14步；这个数量级来到 1,000,000 的话，则差距就更大了，二分查找仅仅最多 20 步就可以完成，线性查找则最多需要 1,000,000。

这里就可以看出合适的算法可以对操作有多么巨大的性能影响了。

当然有序数组并不是所有的操作都要比普通数组快，譬如插入操作；所以我们需要区分应用场景来选择合适的数据结构。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！