JavaScript实现搜索算法(二分搜索，内插搜索，贪心算法，斐波那契查找）
1.二分查找：基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
(1)递归
function binarySearch(data, dest, start, end) {
if (start > end) { // 新增否则找不到进入死循环了
return false;
}
var end = end || data.length - 1;
var start = start || 0;
var mid = Math.floor((start + end) / 2);
//var mid = parseInt(start+(end-start)/2);
//直接命中
if (data[mid] == dest) {
return mid;
}
if (data[mid] > dest) { // 放左
end = mid - 1;
return binarySearch(data, dest, start, end);
} else { // 放右
start = mid + 1;
return binarySearch(data, dest, start, end);
}
return false; (2)非递归
function binarySearch2(data, dest) {
var end = data.length - 1;
var start = 0;
while (start <= end) {
var m = Math.floor((end + 1) / 2);
if (data[m] == dest) {
return m;
}
if (data[m] > dest) {
end = m - 1;
} else {
start = m + 1;
}
}
return falsex 2.插值查找：插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面我们讲的 findVal。mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;对应前面的代码公式： mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
(1)递归：
const insertSearchByRe = (arr, value, start, end) => {
if(start > end) {
return -1
}
let mid = start+(value-arr[start])/(arr[end]-arr[start])*(end-start)
if(arr[mid] == value) {
return mid
} else if(arr[mid] > value) {
end = mid -1
return insertSearchByRe(arr, value, start, end)
} else {
start = mid + 1
return insertSearchByRe(arr, value, start, end)
}
}
(2)非递归: const insertSearch = (arr, value) => {
let start = 0
let end = arr.length - 1
while (start <= end) {
let mid = start+(value-arr[start])/(arr[end]-arr[start])*(end-start)
if (arr[mid] == value) {
return mid
} else if (arr[mid] > value) {
end = mid - 1
} else{
start = mid + 1
}
}
return -1
}
- 时间复杂度：O(log₂(log₂n))
- 应用：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多
最少硬币找零是给出要找零的钱数，以及可以用硬币的额度数量，找出有多少种找零方法。
如：美国面额硬币有：1，5，10，25
我们给36美分的零钱，看能得怎样的结果？
function MinCoinChange(coins){
var coins = coins;
var cache = {};
this.makeChange = function(amount){
var change = [], total = 0;
for(var i = coins.length; i >= 0; i--){
var coin = coins[i];
while(total + coin <= amount){
change.push(coin);
total += coin;
}
}
return change;
}
}
var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
minCoinChange.makeChange(36);
//一个25, 一个10, 一个1 4.https://zhuanlan.zhihu.com/p/262243253 const fib = (maxSize) => {
let f = new Array(maxSize);
f[0] = 1;
f[1] = 1;
for (let i = 2; i < maxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
const fibSearch = (arr, value) => {
let low = 0;
let high = length = arr.length - 1;
let k = 0;
let mid = 0;
let f = fib(20);
while (high > f[k] - 1) {
k++;
};
arr = [...arr];
for (let i = high + 1; i < f[k]; i++) {
arr.push(arr[high]);
}
while (low <= high) {
mid = low + f[k - 1] - 1;
if (value < arr[mid]) {
high = mid - 1;
k--;
} else if (value > arr[mid]) {
low = mid + 1;
k -= 2;
} else {
if (mid <= length) {
return mid;
} else {
return length;
}
}
}
return -1
}
