前端算法详解——二分法(查找、排序、去重、最小值)

前言

• 本文基于递归算法，如不清楚请先移步
• 为什么好多人都在研究算法?
  快，强，省
• 算法核心
  分而治之
• 二分法
  一切东西一分为二; 二分法是一个'万能'方法，几乎可以解决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));