个体户可以做企业网站,网站备案 假通信地址,自己开外包公司怎么接项目,做网站的集团1.前言
常见的查找算法有顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找等。如果进行归类#xff0c;那么二分查找、插值查找#xff08;一种查找算法#xff09;以及斐波那契查找都可以归为插值查找#xff08;大类#xff09;。而插值查找…1.前言
常见的查找算法有顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找等。如果进行归类那么二分查找、插值查找一种查找算法以及斐波那契查找都可以归为插值查找大类。而插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。
这些算法中最重要的就是Hash查找和二分查找。
记住凡是涉及到在排好序的地方全局或部分查找的都可以考虑使用二分查找来优化查找效率
插值查找使用的公式为 x ( k e y − a r r [ i ] ) ( r − i ) a r r [ r ] − a r r [ i ] x \frac{(key-arr[i])(r-i)}{arr[r]-arr[i]} xarr[r]−arr[i](key−arr[i])(r−i) 其中i和r分别代表数组的第一个和最后一个索引 key代表待查找的元素
分块查找是折半查找和顺序查找的一种改进方法分块查找由于只要求索引表是有序的对块内节点没有排序要求因此特别适合解决节点动态变化的情况。
2.基本查找
基本查找也就是顺序查找不需要在乎数组是否排序缺点是效率较低。
function search(arr, key) {for (let index 0; index arr.length; index) {if (arr[index] key) {return index;}}
}3.二分查找与分治
分治就是把整体拆分为局部一个复杂的问题可以拆分成很多相似的小问题。二分查找是将中间结果与目标进行比较一次去掉一半。
3.1 循环方法
// 二分查找——循环方式
function binarySearch(array, low, high, target) {while (low high) {let mid (low high) / 2;if (array[mid] target) {low mid 1} else if (array[mid] target) {high mid - 1;} else {return mid;}}return -1;
}/ 运算符效率较低,可以写成移位符 , 还存在一个问题当low 和 high 过于大时low high可能会溢出可以将 let mid (low high) / 2;改为let mid low ((high - low) 1);,只要low 和 high 没有溢出mid就不会溢出。
最终代码如下
function binarySearch(array, low, high, target) {while (low high) {let mid low ((high - low) 1);if (array[mid] target) {low mid 1} else if (array[mid] target) {high mid - 1;} else {return mid;}}return -1;
}3.2 递归方法
按照递归三步法代码如下
// 二分查找——递归方式
function binarySearch(array, low, high, target) {// 递归终止条件if (low high) {let mid low ((high - low) 1);// 不同情况判断if (array[mid] target) {return mid;} else if (array[mid] target) {return binarySearch(array, mid 1, high, target);} else {return binarySearch(array, low, mid - 1, target);}}// 表示没有搜索到return -1;
}4.有重复元素的二分查找
在上面的基础上如果元素存在重复要求如果重复就找左侧第一个比如[1, 2, 2, 2, 3, 3, 3, 4, 5, 6],要返回第一个2的索引值——1。
分析基于上面简单的二分查找在这里我们找到target不要着急返回而是在重复元素的这个区间继续进行查找一直找到最左侧的重复元素再返回最左侧元素的重复索引。在重复元素的这个区间继续进行查找方法有好几种第一种方法比较简单就是使用线性查找一个一个的向左进行查找直到找到最左侧的重复元素。
// 元素中有重复的二分查找在上面的基础上元素存在重复如果重复则找左侧第一个
function binarySearchOfRepeat(array, target) {// 特判if (array null || array.length 0) {return -1;}let left 0;let right array.length - 1;while (left right) {let mid left ((right - left) 1);if (array[mid] target) {left mid 1;} else if (array[mid] target) {right mid - 1;} else {// 找到目标值后还应该继续向左侧进行线性查找,直到左侧没有重复值while (mid ! 0 array[mid] target) {mid--;}// 如果一直找到了开头还都是重复值就返回开头if (mid 0 array[mid] target) {return mid;}// 不然就返回mid 1return mid 1;}}return -1;
}这里之所以返回mid 1,是因为假如序列为[1, 2, 2, 2, 2, 3, 3]当target3,当内层的while循环退出时nums[mid]2因此必须返回mid 1 第二种方法呢就是使用折半查找
function binarySearchOfRepeat(array, target) {// 特判if (array null || array.length 0) {return -1;}let left 0;let right array.length - 1;while (left right) {let mid left ((right - left) 1);if (target array[mid]) {right mid - 1;} else if (target array[mid]) {left mid 1;} else {// 如果存在重复元素在该段重复数组区间内进行折半查找while (left mid) { let midLeft left ((mid - left) 1);// 如果array[midLeft] target直接去掉一半右边的重复值if (array[midLeft] target) {mid midLeft;} // 如果array[midLeft] ! target说明超过了重复区间让left midLeft 1继续查找else {left midLeft 1;}}return left;}}return -1;
}拓展——使用递归进行有重复元素的二分查找
再拓展一下使用递归方法。
function binarySearchOfRepeat(array, target, left, right) {// 不能发生边界逾矩if (left right) {return -1;}let mid left ((right - left) 1);if (array[mid] target) {// 在重复区间内使用递归来找到最左侧的位置let leftmostInRepeat binarySearchOfRepeat(array, target, left, mid - 1);// 如果没有重复返回mid如果有重复返回重复区间最左侧值索引return (leftmostInRepeat -1) ? mid : leftmostInRepeat;} else if (target array[mid]) {return binarySearchOfRepeat(array, target, left, mid - 1);} else {return binarySearchOfRepeat(array, target, mid 1, right);}
}function findLeftmostRepeatIndex(array, target) {if (array null || array.length 0) {return -1;}return binarySearchOfRepeat(array, target, 0, array.length - 1);
}
