前言
- 本文基于递归算法，如不清楚请先移步
- 为什么好多人都在研究算法?
快，强，省 - 算法核心
分而治之 - 二分法
一切东西一分为二; 二分法是一个'万能'方法，几乎可以解决87%以上的问题。每次排除都把所有的情况分成"可能"和"不可能"两种,然后抛弃所有"不可能"的情况。
1. 从找一个数开始
需求： 查找在有序数组内一个数是否存在(具体实现如下)
function findExis (params) {
const arr = params.arr || [];
const num = params.num;
for (let i = 0; i<arr.length; i++) {
if(arr[i] === num) return true;
}
return false;
}
console.log(findExis({
arr: [1,3,5,478,698,123456],
num: 4782
}));
2. 二分查找
需求：针对一有序数组查找某一个数是否在该数组中。
分析与思路： 二分法，一分为二。将数组分为两个进行查找，若该数小于中间值，则向左查找，否则向右查找。然后递归再次查找（这样每一次都是排除掉一半的不可能）
function find(params){
var arr = params.arr || [];
var start = params.startIndex || 0;
var end = params.endIndex || (arr.length-1);
var n = params.n;
if ( start > end ) {
return false;
} else if( start == end) {
if (arr[start] == end ) {
return true;
}else{
return false;
}
}
var center = Math.floor((start + end)/2);
if(arr[center] == n){
return true;
} else {
if(n<arr[center]){
return find({
n: n,
startIndex: 0,
endIndex: center
});
}else{
return find({
n: n,
startIndex: center+1,
endIndex: end
});
}
}
};
alert(find({
arr: [1,3,5,6567,9812,98121,981211,981211],
n: 65671
}));
3. 二分排序
需求：将无序数组进行排序。
分析与思路： 将原始数组一分为二个数组（left、right），再讲这两个数组利用递归再次进行拆分...最后再将左右两个数组进行排序。
function dichotomySort(arr, start, end) {
if (start > end) {
return [];
} else if (start == end) {
return [arr[start]];
};
var center = Math.floor((start + end) / 2);
var left = dichotomySort(arr, start, center);
var right = dichotomySort(arr, center + 1, end);
var result = [];
while (left.length > 0 || right.length > 0) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
if (left.length == 0) {
result = result.concat(right);
break;
} else if (right.length == 0) {
result = result.concat(left);
break;
}
}
return result;
};
var arr = [12, 233, 5, -90, 23, -80, 8];
alert(dichotomySort(arr, 0, arr.length - 1));
4. 二分法去重
分析与思路：同理将数组一分为二，左右分别去重，在一起去重
function findArray(arr, n) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] == n) return true;
}
return false;
};
function duplicateRemoval(arr, start, end) {
if (start > end) {
return [];
} else if (start == end) {
return [arr[start]];
};
var center = Math.floor((start + end) / 2);
var left = duplicateRemoval(arr, start, center);
var right = duplicateRemoval(arr, center + 1, end);
for (var i = 0; i < right.length; i++) {
if (!findArray(left, right[i])) {
left.push(right[i]);
}
}
return left;
};
var arr = [1, 2, 3, 4, 5, 1, 5, 3];
alert(duplicateRemoval(arr, 0, arr.length - 1));
5.二分法找最小值
function dichotomyMin(arr, start, end) {
if (start > end) {
return false;
} else if (start == end) {
return arr[start];
}
var center = Math.floor((start + end) / 2);
var l = dichotomyMin(arr, start, center);
var r = dichotomyMin(arr, center + 1, end);
if (l < r) {
return l;
} else {
return r;
}
}
var arr = [2, 3, 5, 6567, 9812, 98121, 981211, 981211];
alert(findMin(arr, 0, arr.length - 1));
