一、基础查找算法

1. 线性查找（顺序查找）

原理：逐个遍历数据，直到找到目标。

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

应用场景： • 小规模无序数据（如数组的 indexOf 方法底层实现） • 需要兼容所有浏览器环境的简单查找

2. 二分查找

原理：针对有序数据，通过不断缩小范围定位目标。

function binarySearch(arr, target) {
    let left = 0,
        right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        arr[mid] < target ? left = mid + 1 : right = mid - 1;
    }
    return -1;
}

应用场景： • 有序数组的快速查找（如时间戳排序的日志数据） • 性能敏感场景（时间复杂度 O(log n)）

二、DOM 查找优化

1. 选择器查询

// 高效查询：ID选择器（浏览器哈希表直接定位）
document.getElementById('header');

// 低效查询：复杂CSS选择器（需遍历DOM树）
document.querySelector('div.container > ul.list li:first-child');

优化技巧： • 优先使用 id 选择器 • 避免过度层级嵌套（浏览器从右向左解析选择器）

2. 缓存DOM查询结果

// 错误写法：重复查询
function update() {
    document.getElementById('count').textContent = ++counter;
}

// 正确写法：缓存引用
const countElement = document.getElementById('count');

function update() {
    countElement.textContent = ++counter;
}

三、数据结构优化查找

1. 使用对象/Map快速查找

// 使用对象（类似哈希表）
const users = {
    'user1': {
        id: 1,
        name: 'Alice'
    },
    'user2': {
        id: 2,
        name: 'Bob'
    }
};
console.log(users['user1']); // O(1) 时间复杂度

// 使用Map（支持任意键类型）
const map = new Map();
map.set('key', 'value');
map.get('key');

2. 使用Set检查存在性

const tags = new Set(['js', 'css', 'html']);
console.log(tags.has('js')); // 比数组的includes()更高效

四、高级场景应用

1. 前缀树（Trie）实现搜索建议

class TrieNode {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    insert(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children[c]) node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isEnd = true;
    }
    search(prefix) {
        let node = this.root;
        const result = [];
        for (const c of prefix) {
            if (!node.children[c]) return result;
            node = node.children[c];
        }
        this._dfs(node, prefix, result);
        return result;
    }
    _dfs(node, path, result) {
        if (node.isEnd) result.push(path);
        for (const c in node.children) {
            this._dfs(node.children[c], path + c, result);
        }
    }
}

// 使用示例
const trie = new Trie();
trie.insert('apple');
trie.insert('app');
console.log(trie.search('app')); // ['app', 'apple']

2. 虚拟列表中的二分查找

// 在有序的列表数据中快速定位滚动位置
function findNearestIndex(sortedArray, target) {
    let low = 0,
        high = sortedArray.length - 1;
    while (low <= high) {
        const mid = (low + high) >>> 1;
        if (sortedArray[mid] === target) return mid;
        sortedArray[mid] < target ? low = mid + 1 : high = mid - 1;
    }
    return low; // 返回插入位置
}

五、性能对比建议

方法	时间复杂度	适用场景
线性查找	O(n)	小数据量/无序数据
二分查找	O(log n)	有序数组
哈希表查询	O(1)	键值对数据
Trie树查询	O(k)	前缀匹配（k为关键词长度）

最佳实践建议

1. 数据预处理：对频繁查询的静态数据建立索引
2. 空间换时间：使用Map/Set等数据结构优化查找性能
3. 避免重复计算：对相同查询结果进行缓存（Memoization）
4. Web Worker：对10万+量级数据的复杂查找使用多线程

通过合理选择算法和数据结构，可以显著提升前端应用的响应速度和用户体验。