js:数据结构笔记13--检索算法
2024-10-18 13:21:30
顺序查找：也称线性查找，暴力查找的一种
- 基本格式：
var nums = [];
for(var i = 0; i < 10; ++i) {
nums[i] = Math.floor(Math.random() * 101);
} function seqSearch(arr,data) {
for(var i = 0; i < arr.length; ++i) {
if(arr[i] === data) {
return i;
}
}
return -1;
}
seqSearch(nums,45);
//效率比Array.indexof()低；
- 查找最值：
function findMin(arr) {
var min = arr[0];
for(var i = 1; i < arr.length; ++i) { //这里从第二个开始查找
if(arr[i] < min) { //arr[i] > max
min = arr[i];
}
}
return min;
}
- 自组织数据：经过多次查找之后，查找最频繁的元素会从原来的位置移动到数据集的起始位置
var nums = [0,45,101,12,5,12,78,45,5];
function seqSearch(arr,data) {
for(var i = 0; i < arr.length; ++i) {
if(arr[i] === data) {
if( i > 0) {
swap(arr,i,i-1); //swap(arr,i,0);
//console.log(arr);
}
return true;
}
}
return false;
}
function swap(arr,index,index1) {
temp = arr[index];
arr[index] = arr[index1];
arr[index1] = temp;
}
for(var i = 0; i < 4; ++i) {
seqSearch(nums,5);
}
-----------------------------
[0, 45, 101, 5, 12, 12, 78, 45, 5]
[0, 45, 5, 101, 12, 12, 78, 45, 5]
[0, 5, 45, 101, 12, 12, 78, 45, 5]
[5, 0, 45, 101, 12, 12, 78, 45, 5]
二分查找：如果数据是有序的，二分查找比顺序查找算法更高效；
var nums = [0,5,46,85,102,212,503]; //必须先排序好
function binSearch(arr,data) {
var upperBound = arr.length - 1;
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;
}
console.log(binSearch(nums,46));
- 计算次数：
function count(arr,data) {
var count = 0,
position = binSearch(arr,data);
if(position > -1) {
++count;
for(var i = position-1; i > 0; --i) {
if(arr[i] === data) {
++count;
} else {
break;
}
}
for(var i = position + 1; i < arr.length; ++i) {
if(arr[i] === data) {
++count;
} else {
break;
}
}
}
return count;
}
console.log(count(nums,5));
最新文章
- Android想服务器传图片，透过流的方式。还有读取服务器图片（文件），也通过流的方式。
- PHP数据库基础
- HDU4916 Count on the path(树dp??)
- js----对象的创建
- hadoop2.2.0+hive-0.10.0完全分布式安装方法
- 虚拟主机apache
- weChat聊天发送图片带有小尖角的实现
- CSS引入的方式有哪些? link和@import的区别是?转载
- DRY
- LeetCode——Flatten Binary Tree to Linked List
- 按键（vb）启动指定目录的程序以及获取当前应用路径
- C# EnumHelper Enum的值,Description，ToString()的相互转换
- jQuery-弹幕
- 大数据入门到精通8-spark RDD 复合key 和复合value 的map reduce操作
- SQLServer2008 导出数据库表结构和数据
- 字符串、字节数组、流之间的相互转换以及文件MD5的计算
- Java的OOP三大特征之一——继承
- abp 嵌入资源（视图、css、js）的访问
- day31 python学习 操作系统的介绍，
- Android ListView setOnItemClickListener/setOnItemSelectedListener,无效