javascript数据结构与算法之检索算法

数据之秘：顺序查找与二分查找的奇妙之旅

数据的海洋，如同一片神秘的森林，我们如何在这片森林中寻找到我们想要的信息呢？两大查找方式——顺序查找与二分查找，就是我们手中的明灯。今天，就让我们一起这两种查找方式的奇妙世界。

一、初探顺序查找

想象一下，你在一个元素随机排列的列表里寻找某个数据。顺序查找就是你的得力助手。它从列表的第一个元素开始，逐一判断，直到找到目标或搜索完毕。这就像是在森林中沿着小路一步步寻找。以下是顺序查找的简化代码：

function seqSearch(data, arr){

for(var i = 0; i < arr.length; ++i){

if(arr[i] == data){

return true;

}

}

return false;

}

除了判断数据是否存在，顺序查找还可以帮助我们找到匹配元素的位置。想象一下，你在森林中找到了某种特定的植物，你想知道它在森林中的位置，顺序查找可以帮你做到。代码如下：

二、二分查找的魅力

而二分查找，则适用于已排序的列表。它的效率更高，因为它总是将搜索范围减半，直到找到目标。这就像在森林中，你知道目标的大致方向，可以迅速缩小搜索范围。那么如何在数组中查找最小值和最大值呢？最小值的查找方法是将数组的第一个元素设为最小值，然后遍历数组，如果发现有更小的元素，就更新最小值。最大值的查找方法类似。以下是寻找最小值和最大值的代码示例：

function findMin(arr){

var min = arr[0];

for(var i = 1; i < arr.length; ++i){

if(arr[i] < min){

min = arr[i];

}

}

return min;

}

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

二分查找与重复计数：一段编程之旅

让我们深入了解一下二分查找算法和重复计数算法。这两种算法在编程中非常常见，特别是在处理大规模数据集时。二分查找以其高效性著称，而重复计数则能帮助我们理解数据集中某个元素的重复情况。

让我们理解二分查找的工作原理。这是一种在排序数组中查找特定元素的算法。基本思想是，将数组分为两部分，然后判断目标值是在前半部分还是后半部分，接着再对选定的部分进行同样的操作，直到找到目标值或确定目标值不存在于数组中。以下是二分查找的JavaScript实现：

```javascript

function binSearch(data, arr) {

var lowerBound = 0;

var upperBound = arr.length - 1;

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; // 如果未找到元素，则返回-1

}

```

当二分查找算法找到某个值时，我们想知道这个值在数据集中出现了多少次。这就需要我们实现一个计算重复次数的算法。我们可以利用二分查找的结果作为基础，然后向两边扩展，统计重复元素的数量。以下是计算重复次数的JavaScript实现：

```javascript

function count(data, arr) {

var count = 0; // 初始化计数器为0

var position = binSearch(data, arr); // 获取目标值的位置

if (position > -1) { // 如果找到了目标值

count++; // 统计一次重复次数，并记录位置信息

var arrWithPositions = []; // 存储元素位置信息的数组

arrWithPositions.push({ index: count }); // 记录第一次出现的位置信息

// 向左扩展，统计左侧重复元素数量及位置信息

for (var i = position - 1; i > 0 && arr[i] === data; i--) {

count++; // 增加重复计数次数

arrWithPositions.push({ index: count }); // 记录位置信息到数组中

}

// 向右扩展，统计右侧重复元素数量及位置信息（跳过已记录的位置）

for (var i = position + 1; i < arr.length && arr[i] === data; i++) {