1.查找的定义
在计算机科学中定义为:在一些(有序的/无序的)数据元素中,通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。
2.顺序查找
从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相同,则查找成功;如果直到最后一个(或第一个)记录,关键字和给定值比较都不相等,则查找不成功。
顺序查找的时间复杂度为O(n)。
function orderSearch(target, arr) {
// 也可以使用for循环
let i = arr.length - 1;
while (arr[i] != target && i >= 0) {
i--;
}
return i;
}
3.二分查找
二分查找也叫折半查找,它的前提是线性表中必须是关键码有序(一般是从小到大有序),线性表必须采取线性存储。二分查找是在有序表中,取中间记录作为比较对象,若给定值与中间记录关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区进行查找;若给定值大于中间记录的关键字,则在中间记录的右半区进行查找。不断重复上述过程,直到查找成功或所有查找区域无记录,查找失败。
function halfSearch(target, arr) {
let low = 0;
let high = arr.length - 1;
let i = 0;
// 当low>high时说明此数不存在,循环结束,返回-1,存在等号是因为target有可能出现在第一位或最后一位
while (low <= high) {
i = parseInt((low + high) / 2);
if (target < arr[i]) {
// high 不能等于i,target已经与arr[i]比较过(出现死循环 low=high,但arr[i]!=target)
high = i - 1;
} else if (target > arr[i]) {
// low 不能等于i,target已经与arr[i]比较过i
low = i + 1;
} else {
return i;
}
}
return -1;
}
4.斐波那契查找
斐波那契查找与二分查找的原理和时间复杂度相同,只是mid的值不再是中间值,而是mid=low+fib(k-1)-1。
详细原理可参考:www.cnblogs.com/han200113/p…
function fibSearch(target, arr) {
//简易斐波那契数列
function fib(n) {
if (n <= 1) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
var low = 0;
//记录数组长度,后续会填充数组
const temp = arr.length - 1;
var k = 0;
var mid = 0;
while (fib(k) - 1 < arr.length) {
k++;
}
high = fib(k) - 1;
//将arr数组填充至fib(k)的长度
for (var i = temp; i < high; i++) {
arr.push(arr[temp]);
}
while (low <= high) {
mid = low + fib(k - 1) - 1;
if (arr[mid] < target) {
low = mid + 1;
k = k - 2;
} else if (arr[mid] > target) {
high = mid - 1;
k = k - 1;
} else {
return mid <= temp ? mid : temp;
}
}
return -1;
}
5.二叉排序树
二叉排序树又叫二叉查找树。二叉排序树若它的左子树不为空,则左子树上所有节点的值均小于根节点的值;若它的右子树不为空,则右子树上所有节点的值均大于根节点的值;它的左右子树也是二叉排序树。
二叉排序树的数据结构见上篇。
//二叉排序树的查找
function treeSearch(target, root) {
if (root) {
if (target == root.value) {
return true;
} else if (target < root.value) {
return treeSearch(target, root.left);
} else {
return treeSearch(target, root.right);
}
} else {
return false;
}
}