江苏龙网

  1. 主页 > 生活百科 > >

TypeScript实现八大排序与搜索算法( 九 )

TypeScript

编写测试代码const array = [7, 8, 1, 2, 3, 5, 12, 13, 16, 19];const searchArithmetic = new SearchArithmetic(array, 7);const mid = searchArithmetic.binarySearch();console.log(mid);

TypeScript实现八大排序与搜索算法

文章插图
 
内插搜索内插搜索是改良版的二分搜索 。二分搜索总是检查mid位置上的值，而内插搜索可能会根据要搜索的值检查数组中的不同地方 。
实现思路它遵循以下步骤：
  • 使用position公式选中一个值
  • 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小）
  • 如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找（较大）
实现代码    /**     * 内插搜索     *  二分查找的优化，通过特定算法计算delta和position的值优化掉二分查找的寻找中间值做法     * @param equalsFn 校验两个值是否相等函数     * @param diffFn 计算两个数的差值函数     */    interpolationSearch(equalsFn = defaultEquals, diffFn: IDiffFunction<T> = defaultDiff): number | null {        // 排序        this.sort.quickSort();        // 获取数组程度        const { length } = this.array;        // 定义指针，确定数组边界        let low = 0;        let high = length - 1;        // 声明position，用于公式        let position = -1;        let delta = -1;        // 目标值大于等于数组的low边界值且目标值小于等于high边界值就执行循环里的内容        while (low <= high && biggerEquals(this.target, this.array[low], this.compareFn) && lesserEquals(this.target, this.array[high], this.compareFn)) {            // 目标值与array的low边界的值做差            // 与array的high边界的值和low边界的值做差            // 最后将二者得出的值做除法运算，计算出delta值            delta = diffFn(this.target, this.array[low]) / diffFn(this.array[high], this.array[low]);            // 计算比较值的位置            position = low + Math.floor((high - low) * delta);            // 如果比较值位置的元素等于目标值，则返回当前索引            if (equalsFn(this.array[position], this.target)) {                return position;            }            // 如果比较值位置的元素小于目标值，则向其右边继续找            if (this.compareFn(this.array[position], this.target) === Compare.LESS_THAN) {                low = position + 1;            } else {                // 如果比较值位置的元素大于目标值，则向其左边继续查找                high = position - 1;            }        }        // 未找到        return null;    }


推荐阅读


上一篇：详解DBSCAN聚类

下一篇：面向对象编程OOP的基本概念