javascript数据结构与算法之检索算法
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
查找数据有2种方式，顺序查找和二分查找。顺序查找适用于元素随机排列的列表。二分查找适用于元素已排序的列表。二分查找效率更高，但是必须是已经排好序的列表元素集合。
一：顺序查找
顺序查找是从列表的第一个元素开始对列表元素逐个进行判断，直到找到了想要的结果，或者直到列表的结尾都没有找到想要找的元素。
代码如下：
function seqSearch(data,arr) {
for(var i = 0; i < arr.length; ++i) {
if(arr[i] == data) {
return true;
}
}
return false;
}
我们也可以返回匹配元素位置的顺序查找函数，代码如下：
function seqSearch(data,arr) {
for(var i = 0; i < arr.length; ++i) {
if(arr[i] == data) {
return i;
}
}
return -1;
}
二：查找最小值和最大值
在数组中查找最小值算法如下：
1. 将数组第一个元素赋值给一个变量，把这个变量作为最小值。
2. 开始遍历数组，从第二个元素依次同当前最小值进行比较。
3. 如果当前元素的数值小于当前最小值，则将当前元素设为新的最小值。
4. 移动到下一个元素，重复步骤3.
5. 当程序结束时，这个变量中存储的就是最小值。
代码如下：
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;
}
三：二分查找法。
如果你要查找的数据是有序的，二分查找算法比顺序查找算法效率更高。二分查找算法基本原理如下：
1. 将数组的第一个位置设置为下边界(0).
2. 将数组的最后一个元素所在的位置设置为上边界(数组的长度减1)。
3. 若下边界等于或小于上边界，则做如下操作：
A. 将中点设置为(上边界加上下边界) 除以2.
B. 如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加1.
C. 如果中点的元素大于查询的值，则将上边界设置为中点元素所在下标减1.
D. 否则中点元素即为要查找 的数据，可以进行返回。
代码如下：
// 二分查找算法
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;
}
// 快速排序
function qSort(list) {
if(list.length == 0) {
return [];
}
// 存储小于基准值的值
var left = [];
// 存储大于基准值的值
var right = [];
var pivot = list[0];
for(var i = 1; i < list.length; i++) {
if(list[i] < pivot) {
left.push(list[i]);
}else {
right.push(list[i])
}
}
return qSort(left).concat(pivot,qSort(right));
}
// 测试代码
var numbers = [0,9,1,8,7,6,2,3,5,4];
var list = qSort(numbers);
console.log(binSearch(6,list));
四：计算重复次数；
当二分查找算法binSearch()函数找到某个值时，如果在数据集中还有其他相同的值出现，那么该函数会定位在类似值附近，换句话说，其他相同的值可能会出现已找到值的左边或者右边。
那么我们最简单的方案是写2个循环，一个同时对数据集向下遍历或者向左遍历，统计重复次数；然后，向上或向右遍历，统计重复次数。代码如下：
// 计算重复次数
function count(data,arr) {
var count = 0;
var arrs = [];
var position = binSearch(data,arr);
if(position > -1) {
++count;
arrs.push({"index":count});
for(var i = position -1; i > 0; --i) {
if(arr[i] == data) {
++count;
arrs.push({"index":count});
}else {
break;
}
}
for(var i = position + 1; i < arr.length; ++i) {
if(arr[i] == data) {
++count;
arrs.push({"index":count});
}else {
break;
}
}
}
return arrs;
}
// 测试重复次数的代码
var arr = [0,1,1,1,2,3,4,5,6,7,8,9];
var arrs = count(1,arr);
console.log(arrs);
console.log(arrs.length);
如下图所示：
相关文章
这篇文章主要介绍了微信小程序之分享页面如何返回首页的示例，小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧2018-03-03
这篇文章主要介绍了JS基础之逻辑结构与循环操作,结合实例形式分析了JavaScript逻辑判断、流程控制、循环语句等相关操作技巧,需要的朋友可以参考下2020-01-01
本篇文章是对在JS中Map和List的简单实现代码进行了详细的分析介绍，需要的朋友参考下2013-07-07
这篇文章主要介绍了JS浅拷贝和深拷贝原理与实现方法,结合实例形式分析了javascript浅拷贝及深拷贝相关概念、原理、实现方法与操作注意事项,需要的朋友可以参考下2019-02-02
在Web应用程序特别是Web2.0程序开发中，经常要获取页面中某个元素，然后更新该元素的样式、内容等。如何获取要更新的元素，是首先要解决的问题。2009-08-08
这篇文章主要介绍了基于javascript实现彩票随机数生成的相关资料，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下2016-01-01
这篇文章主要介绍了iframe窗口高度自适应的实现方法，有需要的朋友可以参考一下2014-01-01
这篇文章主要为大家详细介绍了js手机号批量滚动抽奖实现代码，s适用于年会等活动，具有一定的参考价值，感兴趣的小伙伴们可以参考一下2017-01-01
这篇文章主要介绍了JS 设计模式之：工厂模式,结合实例形式分析了JS 工厂模式基本概念、原理、定义、实现方法与操作注意事项,需要的朋友可以参考下2020-05-05
这篇文章主要为大家详细介绍了小程序拖动区域实现排序效果，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下2022-09-09
最新评论