ArayTS

Appearance

二分查找 ​

一种非常高效的查找算法，通常用于在一个已排序的数组中查找特定目标值。由于其时间复杂度是 O(log n)，它非常适合用于大数据集中的查找操作。

搜索排序列表或数组中的数据 ​

当需要在一个已排序的数据集（如数字、字母、日期等）中快速查找某个元素时，二分查找可以提供比线性查找更高效的解决方案。

🔶电商平台：当用户筛选商品列表（如按价格、销量、评分等排序）时，可以使用二分查找快速找到符合条件的商品。

🔶搜索引擎：对于已经排序的搜索结果，可以使用二分查找来定位某个关键字或相关内容。

ts
const sortedList = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const target = 7;

const index = binarySearch(sortedList, target);
console.log(index); // 输出：3，表示目标值7在数组中的索引

动态查询和筛选数据 ​

在前端中，常常需要根据用户输入的条件实时筛选数据。例如，如果在一个大的排序数据列表中，用户希望输入一个目标数值或条件进行快速查找，二分查找是一个很好的选择。

🔶社交媒体：在已按发布时间排序的帖子列表中，用户输入特定的时间戳，应用可以通过二分查找找到特定时间点的帖子。

🔶图表数据点：在图表应用中，当用户鼠标悬停或点击时，可以使用二分查找快速定位特定数据点。

ts
const timestamps = [1615400400000, 1615404000000, 1615407600000, 1615411200000]; // 排序的时间戳
const targetTimestamp = 1615404000000;

const index = binarySearch(timestamps, targetTimestamp);
console.log(index); // 输出：1，表示目标时间戳在数组中的索引

游戏中找寻最佳匹配 ​

在一些游戏或实时系统中，需要根据某些条件（如玩家的等级、分数等）来快速查找最佳匹配项。二分查找可以帮助实现这种快速查找。

🔶匹配系统：当需要根据玩家的排名或分数找到合适的匹配对手时，二分查找可以用来快速找到符合条件的玩家。

ts
const playerScores = [100, 200, 300, 400, 500];
const targetScore = 400;

const index = binarySearch(playerScores, targetScore);
console.log(index); // 输出：3，表示目标分数400在数组中的索引

处理有序数据集的范围查询 ​

在数据分析和数据可视化中，往往需要从一个排序的数据集中找到某个特定的范围。二分查找可以帮助定位范围的起始位置和结束位置。

🔶时间序列数据查询：在历史数据分析中，二分查找可以用来快速定位某一特定日期范围内的数据。

🔶分数区间查询：在成绩排名系统中，二分查找可以帮助找到某一分数区间内的排名。

ts
const scores = [50, 60, 70, 80, 90, 100];
const targetScore = 75;

const index = binarySearch(scores, targetScore);
console.log(index); // 输出：-1，表示目标分数不在列表中

实现某些数学算法 ​

在一些前端的数学计算中，二分查找可以用来计算某些函数的根或在给定精度下找到最优解。例如，在计算平方根、立方根等时，可以使用二分查找找到精确值。

🔶精确计算：例如计算一个数的平方根，二分查找可以在一个精度范围内找到该数的平方根。

ts
const findSquareRoot = (n: number): number => {
    let left = 0, right = n;
    const epsilon = 0.0001; // 精度

    while (left <= right) {
        const mid = (left + right) / 2;
        const square = mid * mid;

        if (Math.abs(square - n) < epsilon) {
            return mid;
        } else if (square < n) {
            left = mid + epsilon;
        } else {
            right = mid - epsilon;
        }
    }

    return -1; // 未找到
};

const result = findSquareRoot(25);
console.log(result); // 输出：5，表示25的平方根