返回首页

🔍 查找与高级算法

掌握高效的查找技术，包括二分查找、哈希表、双指针、拓扑排序、并查集等核心算法

基础查找算法

📍 顺序查找 (Linear Search)

最基础的查找算法，逐个遍历数组元素直到找到目标值或遍历完所有元素。适用于无序数组，时间复杂度为 O(n)。

⭐ 难度：入门 📦 空间：O(1)
时间复杂度
最好情况: O(1)
最坏情况: O(n)
平均情况: O(n)
查看代码示例 
# 顺序查找
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = linear_search(arr, 22)
print(f"元素索引：{result}")
// 顺序查找
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// 使用示例
const arr = [64, 34, 25, 12, 22, 11, 90];
const result = linearSearch(arr, 22);
console.log(`元素索引：${result}`);
// 顺序查找
func linearSearch(arr []int, target int) int {
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            return i
        }
    }
    return -1
}

// 使用示例
func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    result := linearSearch(arr, 22)
    fmt.Printf("元素索引：%d\n", result)
}

🎯 二分查找 (Binary Search)

在有序数组中高效查找目标值的算法。每次将查找范围缩小一半，时间复杂度为 O(log n)。是面试和实际应用中最常用的查找算法之一。

⭐ 难度：入门 📦 空间：O(1) 🔑 关键：数组必须有序
时间复杂度
最好情况: O(1)
最坏情况: O(log n)
平均情况: O(log n)
查看代码示例 
# 二分查找 - 迭代实现
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # 防止溢出
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# 二分查找 - 递归实现
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1

    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 使用示例
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
result = binary_search(arr, 7)
print(f"元素索引：{result}")  # 输出：3
// 二分查找 - 迭代实现
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// 二分查找 - 递归实现
function binarySearchRecursive(arr, target, left, right) {
    if (left > right) {
        return -1;
    }
    
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

// 使用示例
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const result = binarySearch(arr, 7);
console.log(`元素索引：${result}`);
// 二分查找 - 迭代实现
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    
    for left <= right {
        mid := left + (right - left) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return -1
}

// 二分查找 - 递归实现
func binarySearchRecursive(arr []int, target, left, right int) int {
    if left > right {
        return -1
    }
    
    mid := left + (right - left) / 2
    if arr[mid] == target {
        return mid
    } else if arr[mid] < target {
        return binarySearchRecursive(arr, target, mid + 1, right)
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1)
    }
}

// 使用示例
func main() {
    arr := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
    result := binarySearch(arr, 7)
    fmt.Printf("元素索引：%d\n", result)
}
常见变体
  • 查找第一个等于目标值的位置 - 当找到目标值时不立即返回，继续向左查找
  • 查找最后一个等于目标值的位置 - 当找到目标值时不立即返回，继续向右查找
  • 查找第一个大于等于目标值的位置 - 下界查找 (lower_bound)
  • 查找第一个大于目标值的位置 - 上界查找 (upper_bound)

哈希表查找

🗂️ 哈希表 (Hash Table)

通过哈希函数将键映射到数组索引，实现平均 O(1)时间复杂度的查找。是解决查找问题的利器，广泛应用于缓存、数据库索引、集合去重等场景。

⭐ 难度：入门 📦 空间：O(n) ⚡ 平均查找：O(1)
时间复杂度
最好情况: O(1)
最坏情况: O(n)
平均情况: O(1)
查看代码示例 
# 哈希表查找示例 - 两数之和
def two_sum(nums, target):
    """
    两数之和问题 - 哈希表经典应用
    在数组中找到两个数，使其和等于目标值
    """
    hash_map = {}  # 存储 {数值：索引}

    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i

    return []

# 使用示例
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"索引：{result}")  # 输出：[0, 1]

# 哈希表实现 - 开放地址法
class HashTable:
    def __init__(self, size=16):
        self.size = size
        self.table = [None] * size

    def _hash(self, key):
        return hash(key) % self.size

    def _probe(self, index):
        """线性探测解决冲突"""
        return (index + 1) % self.size

    def insert(self, key, value):
        index = self._hash(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = self._probe(index)
        self.table[index] = (key, value)

    def search(self, key):
        index = self._hash(key)
        start = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = self._probe(index)
            if index == start:
                break
        return None

# 使用示例
ht = HashTable()
ht.insert("name", "Alice")
ht.insert("age", 25)
print(f"查找 name: {ht.search('name')}")  # 输出：Alice
// 哈希表查找示例 - 两数之和
function twoSum(nums, target) {
    const hashMap = new Map();  // 存储 {数值：索引}

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (hashMap.has(complement)) {
            return [hashMap.get(complement), i];
        }
        hashMap.set(nums[i], i);
    }

    return [];
}

// 使用示例
const nums = [2, 7, 11, 15];
const target = 9;
const result = twoSum(nums, target);
console.log(`索引：${result}`);  // 输出：[0, 1]

// 哈希表实现 - 链地址法解决冲突
class HashTable {
    constructor(size = 16) {
        this.size = size;
        this.table = new Array(size).fill(null).map(() => []);
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i)) % this.size;
        }
        return hash;
    }

    insert(key, value) {
        const index = this._hash(key);
        const bucket = this.table[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value;
                return;
            }
        }
        bucket.push([key, value]);
    }

    search(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                return bucket[i][1];
            }
        }
        return null;
    }
}

// 使用示例
const ht = new HashTable();
ht.insert("name", "Alice");
ht.insert("age", 25);
console.log(`查找 name: ${ht.search('name')}`);  // 输出：Alice
// 哈希表查找示例 - 两数之和
func twoSum(nums []int, target int) []int {
    hashMap := make(map[int]int)  // 存储 {数值：索引}

    for i, num := range nums {
        complement := target - num
        if idx, ok := hashMap[complement]; ok {
            return []int{idx, i}
        }
        hashMap[num] = i
    }

    return []int{}
}

// 哈希表实现 - 链地址法解决冲突
type HashTable struct {
    size  int
    table [][][2]interface{}  // 每个桶是一个链表
}

func NewHashTable(size int) *HashTable {
    return &HashTable{
        size:  size,
        table: make([][][2]interface{}, size),
    }
}

func (ht *HashTable) hash(key string) int {
    hash := 0
    for _, c := range key {
        hash = (hash + int(c)) % ht.size
    }
    return hash
}

func (ht *HashTable) Insert(key string, value interface{}) {
    index := ht.hash(key)
    bucket := ht.table[index]
    for i, item := range bucket {
        if item[0] == key {
            bucket[i][1] = value
            return
        }
    }
    ht.table[index] = append(bucket, [2]interface{}{key, value})
}

func (ht *HashTable) Search(key string) interface{} {
    index := ht.hash(key)
    bucket := ht.table[index]
    for _, item := range bucket {
        if item[0] == key {
            return item[1]
        }
    }
    return nil
}

// 使用示例
func main() {
    // 两数之和示例
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Printf("索引：%v\n", result)  // 输出：[0, 1]

    // 哈希表示例
    ht := NewHashTable(16)
    ht.Insert("name", "Alice")
    ht.Insert("age", 25)
    fmt.Printf("查找 name: %v\n", ht.Search("name"))  // 输出：Alice
}
冲突解决方法
  • 链地址法 (Chaining) - 每个桶维护一个链表，冲突元素挂在链上
  • 开放地址法 (Open Addressing) - 线性探测、二次探测、双重哈希
  • 再哈希法 (Rehashing) - 使用多个哈希函数

双指针技巧

👆👇 双指针 (Two Pointers)

使用两个指针在数组或链表上移动，通过调整指针位置来缩小查找范围。常用于有序数组的查找、链表问题、滑动窗口等场景。

⭐ 难度：入门 📦 空间：O(1) ⚡ 时间：O(n)
常见模式
  • 相向双指针 - 两指针从两端向中间移动，如两数之和、三数之和
  • 同向双指针 - 快慢指针，如链表找中点、判断环
  • 滑动窗口 - 维护一个区间，如最长无重复子串
查看代码示例 
# 相向双指针 - 两数之和 II (有序数组)
def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 索引从 1 开始
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

# 快慢指针 - 判断链表是否有环
def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

# 快慢指针 - 找链表中点
def find_middle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

# 滑动窗口 - 最长无重复字符子串
def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

# 使用示例
numbers = [1, 2, 4, 6, 8, 10]
result = two_sum_sorted(numbers, 8)
print(f"索引：{result}")  # 输出：[1, 3] (2+6=8)
// 相向双指针 - 两数之和 II (有序数组)
function twoSumSorted(numbers, target) {
    let left = 0, right = numbers.length - 1;

    while (left < right) {
        const currentSum = numbers[left] + numbers[right];
        if (currentSum === target) {
            return [left + 1, right + 1];  // 索引从 1 开始
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }

    return [];
}

// 快慢指针 - 判断链表是否有环
function hasCycle(head) {
    let slow = head, fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            return true;
        }
    }

    return false;
}

// 快慢指针 - 找链表中点
function findMiddle(head) {
    let slow = head, fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

// 滑动窗口 - 最长无重复字符子串
function lengthOfLongestSubstring(s) {
    const charSet = new Set();
    let left = 0, maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

// 使用示例
const numbers = [1, 2, 4, 6, 8, 10];
const result = twoSumSorted(numbers, 8);
console.log(`索引：${result}`);  // 输出：[1, 3] (2+6=8)
// 相向双指针 - 两数之和 II (有序数组)
func twoSumSorted(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1

    for left < right {
        currentSum := numbers[left] + numbers[right]
        if currentSum == target {
            return []int{left + 1, right + 1}  // 索引从 1 开始
        } else if currentSum < target {
            left++
        } else {
            right--
        }
    }

    return []int{}
}

// 链表节点定义
type ListNode struct {
    Val  int
    Next *ListNode
}

// 快慢指针 - 判断链表是否有环
func hasCycle(head *ListNode) bool {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }

    return false
}

// 快慢指针 - 找链表中点
func findMiddle(head *ListNode) *ListNode {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    return slow
}

// 滑动窗口 - 最长无重复字符子串
func lengthOfLongestSubstring(s string) int {
    charSet := make(map[byte]bool)
    left, maxLength := 0, 0

    for right := 0; right < len(s); right++ {
        for charSet[s[right]] {
            delete(charSet, s[left])
            left++
        }
        charSet[s[right]] = true
        if right-left+1 > maxLength {
            maxLength = right - left + 1
        }
    }

    return maxLength
}

// 使用示例
func main() {
    numbers := []int{1, 2, 4, 6, 8, 10}
    result := twoSumSorted(numbers, 8)
    fmt.Printf("索引：%v\n", result)  // 输出：[1, 3] (2+6=8)
}

搜索算法

🌊 广度优先搜索 (BFS)

从起始节点开始，逐层向外扩展搜索。使用队列实现，常用于找最短路径、层序遍历、连通性问题等。

⭐ 难度：进阶 📦 空间：O(V) ⚡ 时间：O(V+E)
查看代码示例 
from collections import deque

def bfs(graph, start, target):
    """
    BFS 模板 - 找最短路径
    graph: 邻接表表示的图 {节点：[邻居列表]}
    """
    queue = deque([(start, 0)])  # (节点，距离)
    visited = {start}

    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1  # 未找到

# BFS - 层序遍历
def level_order(graph, start):
    """按层遍历图的节点"""
    queue = deque([start])
    visited = {start}
    result = []

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node)
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        result.append(level)

    return result

# 使用示例 - 迷宫最短路径
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}
result = bfs(graph, 0, 5)
print(f"最短距离：{result}")  # 输出：2
print(f"层序遍历：{level_order(graph, 0)}")  # 输出：[[0], [1, 2], [3, 4, 5]]
// BFS 模板 - 找最短路径
function bfs(graph, start, target) {
    const queue = [[start, 0]];  // [节点，距离]
    const visited = new Set([start]);

    while (queue.length > 0) {
        const [node, dist] = queue.shift();
        if (node === target) {
            return dist;
        }

        const neighbors = graph.get(node) || [];
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, dist + 1]);
            }
        }
    }

    return -1;  // 未找到
}

// BFS - 层序遍历
function levelOrder(graph, start) {
    const queue = [start];
    const visited = new Set([start]);
    const result = [];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const level = [];
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            level.push(node);
            const neighbors = graph.get(node) || [];
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        result.push(level);
    }

    return result;
}

// 使用示例 - 迷宫最短路径
const graph = new Map([
    [0, [1, 2]],
    [1, [0, 3, 4]],
    [2, [0, 5]],
    [3, [1]],
    [4, [1, 5]],
    [5, [2, 4]]
]);
const result = bfs(graph, 0, 5);
console.log(`最短距离：${result}`);  // 输出：2
console.log(`层序遍历：${JSON.stringify(levelOrder(graph, 0))}`);  // 输出：[[0], [1, 2], [3, 4, 5]]
import "container/list"

// BFS 模板 - 找最短路径
func bfs(graph map[int][]int, start, target int) int {
    queue := list.New()
    queue.PushBack([]int{start, 0})  // [节点，距离]
    visited := map[int]bool{start: true}

    for queue.Len() > 0 {
        element := queue.Front()
        queue.Remove(element)
        nodeDist := element.Value.([]int)
        node, dist := nodeDist[0], nodeDist[1]

        if node == target {
            return dist
        }

        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue.PushBack([]int{neighbor, dist + 1})
            }
        }
    }

    return -1  // 未找到
}

// BFS - 层序遍历
func levelOrder(graph map[int][]int, start int) [][]int {
    queue := list.New()
    queue.PushBack(start)
    visited := map[int]bool{start: true}
    var result [][]int

    for queue.Len() > 0 {
        levelSize := queue.Len()
        var level []int

        for i := 0; i < levelSize; i++ {
            element := queue.Front()
            queue.Remove(element)
            node := element.Value.(int)
            level = append(level, node)

            for _, neighbor := range graph[node] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue.PushBack(neighbor)
                }
            }
        }
        result = append(result, level)
    }

    return result
}

// 使用示例
func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 3, 4},
        2: {0, 5},
        3: {1},
        4: {1, 5},
        5: {2, 4},
    }
    result := bfs(graph, 0, 5)
    fmt.Printf("最短距离：%d\n", result)  // 输出：2
    fmt.Printf("层序遍历：%v\n", levelOrder(graph, 0))  // 输出：[[0] [1 2] [3 4 5]]
}

🌲 深度优先搜索 (DFS)

从起始节点开始，沿着一条路径深入到底，然后回溯。使用递归或栈实现，常用于遍历、连通性判断、拓扑排序等。

⭐ 难度：进阶 📦 空间：O(V) ⚡ 时间：O(V+E)
查看代码示例 
def dfs(graph, node, visited=None):
    """
    DFS 模板 - 递归实现
    """
    if visited is None:
        visited = set()

    visited.add(node)
    print(node, end=' ')  # 访问节点

    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

    return visited

# DFS - 迭代实现 (使用栈)
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            # 逆序入栈，保证正序访问
            stack.extend(reversed(graph.get(node, [])))

    return visited

# DFS - 找路径
def dfs_find_path(graph, start, target, path=None):
    """找到从 start 到 target 的一条路径"""
    if path is None:
        path = []
    path = path + [start]

    if start == target:
        return path

    for neighbor in graph.get(start, []):
        if neighbor not in path:
            new_path = dfs_find_path(graph, neighbor, target, path)
            if new_path:
                return new_path

    return None

# 使用示例
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}
print("DFS 遍历:")
dfs(graph, 0)  # 输出：0 1 3 4 5 2
print("\nDFS 找路径:", dfs_find_path(graph, 0, 5))  # 输出：[0, 1, 4, 5]
// DFS 模板 - 递归实现
function dfs(graph, node, visited = new Set()) {
    visited.add(node);
    console.log(node);  // 访问节点

    const neighbors = graph.get(node) || [];
    for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }

    return visited;
}

// DFS - 迭代实现 (使用栈)
function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];

    while (stack.length > 0) {
        const node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node);
            // 逆序入栈，保证正序访问
            const neighbors = graph.get(node) || [];
            for (let i = neighbors.length - 1; i >= 0; i--) {
                if (!visited.has(neighbors[i])) {
                    stack.push(neighbors[i]);
                }
            }
        }
    }

    return visited;
}

// DFS - 找路径
function dfsFindPath(graph, start, target, path = []) {
    path = [...path, start];

    if (start === target) {
        return path;
    }

    const neighbors = graph.get(start) || [];
    for (const neighbor of neighbors) {
        if (!path.includes(neighbor)) {
            const newPath = dfsFindPath(graph, neighbor, target, path);
            if (newPath) {
                return newPath;
            }
        }
    }

    return null;
}

// 使用示例
const graph = new Map([
    [0, [1, 2]],
    [1, [0, 3, 4]],
    [2, [0, 5]],
    [3, [1]],
    [4, [1, 5]],
    [5, [2, 4]]
]);
console.log("DFS 遍历:");
dfs(graph, 0);  // 输出：0 1 3 4 5 2
console.log("DFS 找路径:", dfsFindPath(graph, 0, 5));  // 输出：[0, 1, 4, 5]
// DFS 模板 - 递归实现
func dfs(graph map[int][]int, node int, visited map[int]bool) {
    visited[node] = true
    fmt.Print(node, " ")  // 访问节点

    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited)
        }
    }
}

// DFS - 迭代实现 (使用栈)
func dfsIterative(graph map[int][]int, start int) map[int]bool {
    visited := make(map[int]bool)
    stack := []int{start}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if !visited[node] {
            visited[node] = true
            fmt.Print(node, " ")
            // 逆序入栈，保证正序访问
            neighbors := graph[node]
            for i := len(neighbors) - 1; i >= 0; i-- {
                if !visited[neighbors[i]] {
                    stack = append(stack, neighbors[i])
                }
            }
        }
    }

    return visited
}

// DFS - 找路径
func dfsFindPath(graph map[int][]int, start, target int, path []int) []int {
    path = append(path, start)

    if start == target {
        return path
    }

    for _, neighbor := range graph[start] {
        found := false
        for _, p := range path {
            if p == neighbor {
                found = true
                break
            }
        }
        if !found {
            newPath := dfsFindPath(graph, neighbor, target, path)
            if newPath != nil {
                return newPath
            }
        }
    }

    return nil
}

// 使用示例
func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 3, 4},
        2: {0, 5},
        3: {1},
        4: {1, 5},
        5: {2, 4},
    }
    fmt.Println("DFS 遍历:")
    visited := make(map[int]bool)
    dfs(graph, 0, visited)  // 输出：0 1 3 4 5 2
    fmt.Println("\nDFS 找路径:", dfsFindPath(graph, 0, 5, []int{}))  // 输出：[0 1 4 5]
}

其他查找技巧

🌳 树形查找 (BST Search)

利用二叉搜索树的性质进行查找，左子树所有节点小于根节点，右子树所有节点大于根节点。平均时间复杂度 O(log n)。

⭐ 难度：进阶 📦 空间：O(h) ⚡ 平均：O(log n)
查看代码示例 
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

# BST 查找 - 递归
def search_bst(root, target):
    if not root:
        return None
    if root.val == target:
        return root
    elif root.val < target:
        return search_bst(root.right, target)
    else:
        return search_bst(root.left, target)

# BST 查找 - 迭代
def search_bst_iterative(root, target):
    current = root
    while current:
        if current.val == target:
            return current
        elif current.val < target:
            current = current.right
        else:
            current = current.left
    return None

# BST 插入
def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

# BST 查找最小值
def find_min(root):
    current = root
    while current and current.left:
        current = current.left
    return current

# 使用示例
root = None
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert_bst(root, val)

result = search_bst(root, 6)
print(f"找到节点值：{result.val}" if result else "未找到")

result = search_bst_iterative(root, 13)
print(f"找到节点值：{result.val}" if result else "未找到")

min_node = find_min(root)
print(f"最小值：{min_node.val}")
// BST 节点定义
class TreeNode {
    constructor(val = 0) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// BST 查找 - 递归
function searchBST(root, target) {
    if (!root) {
        return null;
    }
    if (root.val === target) {
        return root;
    } else if (root.val < target) {
        return searchBST(root.right, target);
    } else {
        return searchBST(root.left, target);
    }
}

// BST 查找 - 迭代
function searchBSTIterative(root, target) {
    let current = root;
    while (current) {
        if (current.val === target) {
            return current;
        } else if (current.val < target) {
            current = current.right;
        } else {
            current = current.left;
        }
    }
    return null;
}

// BST 插入
function insertBST(root, val) {
    if (!root) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insertBST(root.left, val);
    } else {
        root.right = insertBST(root.right, val);
    }
    return root;
}

// BST 查找最小值
function findMin(root) {
    let current = root;
    while (current && current.left) {
        current = current.left;
    }
    return current;
}

// 使用示例
let root = null;
for (const val of [8, 3, 10, 1, 6, 14, 4, 7, 13]) {
    root = insertBST(root, val);
}

let result = searchBST(root, 6);
console.log(result ? `找到节点值：${result.val}` : "未找到");

result = searchBSTIterative(root, 13);
console.log(result ? `找到节点值：${result.val}` : "未找到");

const minNode = findMin(root);
console.log(`最小值：${minNode.val}`);
// BST 节点定义
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// BST 查找 - 递归
func searchBST(root *TreeNode, target int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == target {
        return root
    } else if root.Val < target {
        return searchBST(root.Right, target)
    } else {
        return searchBST(root.Left, target)
    }
}

// BST 查找 - 迭代
func searchBSTIterative(root *TreeNode, target int) *TreeNode {
    current := root
    for current != nil {
        if current.Val == target {
            return current
        } else if current.Val < target {
            current = current.Right
        } else {
            current = current.Left
        }
    }
    return nil
}

// BST 插入
func insertBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    if val < root.Val {
        root.Left = insertBST(root.Left, val)
    } else {
        root.Right = insertBST(root.Right, val)
    }
    return root
}

// BST 查找最小值
func findMin(root *TreeNode) *TreeNode {
    current := root
    for current != nil && current.Left != nil {
        current = current.Left
    }
    return current
}

// 使用示例
func main() {
    var root *TreeNode
    for _, val := range []int{8, 3, 10, 1, 6, 14, 4, 7, 13} {
        root = insertBST(root, val)
    }

    result := searchBST(root, 6)
    if result != nil {
        fmt.Printf("找到节点值：%d\n", result.Val)
    } else {
        fmt.Println("未找到")
    }

    result = searchBSTIterative(root, 13)
    if result != nil {
        fmt.Printf("找到节点值：%d\n", result.Val)
    } else {
        fmt.Println("未找到")
    }

    minNode := findMin(root)
    fmt.Printf("最小值：%d\n", minNode.Val)
}

🔢 分块查找 (Block Search)

将数组分成若干块，块内元素无序，但块间有序。先确定目标在哪一块，再在块内进行顺序查找。是顺序查找和二分查找的折中方案。

⭐ 难度：进阶 📦 空间：O(√n) ⚡ 时间：O(√n)

🎲 插值查找 (Interpolation Search)

二分查找的改进版，根据目标值自适应地选择分割点。适用于均匀分布的有序数组，平均时间复杂度可达 O(log log n)。

⭐ 难度：高级 📦 空间：O(1) ⚡ 平均：O(log log n)
查看代码示例 
# 插值查找
def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right and arr[left] <= target <= arr[right]:
        if left == right:
            return left if arr[left] == target else -1

        # 自适应计算 mid 位置
        mid = left + int((target - arr[left]) * (right - left) /
                        (arr[right] - arr[left]))

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# 插值查找 - 递归版本
def interpolation_search_recursive(arr, target, left, right):
    if left > right or target < arr[left] or target > arr[right]:
        return -1

    if left == right:
        return left if arr[left] == target else -1

    # 自适应计算 mid 位置
    mid = left + int((target - arr[left]) * (right - left) /
                    (arr[right] - arr[left]))

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return interpolation_search_recursive(arr, target, mid + 1, right)
    else:
        return interpolation_search_recursive(arr, target, left, mid - 1)

# 使用示例 - 均匀分布数组
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
result = interpolation_search(arr, 60)
print(f"索引：{result}")  # 输出：5

result = interpolation_search(arr, 85)
print(f"索引：{result}")  # 输出：-1 (不存在)
// 插值查找
function interpolationSearch(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right && arr[left] <= target && target <= arr[right]) {
        if (left === right) {
            return arr[left] === target ? left : -1;
        }

        // 自适应计算 mid 位置
        const mid = left + Math.floor((target - arr[left]) * (right - left) /
                                      (arr[right] - arr[left]));

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

// 插值查找 - 递归版本
function interpolationSearchRecursive(arr, target, left, right) {
    if (left > right || target < arr[left] || target > arr[right]) {
        return -1;
    }

    if (left === right) {
        return arr[left] === target ? left : -1;
    }

    // 自适应计算 mid 位置
    const mid = left + Math.floor((target - arr[left]) * (right - left) /
                                  (arr[right] - arr[left]));

    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] < target) {
        return interpolationSearchRecursive(arr, target, mid + 1, right);
    } else {
        return interpolationSearchRecursive(arr, target, left, mid - 1);
    }
}

// 使用示例 - 均匀分布数组
const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
const result = interpolationSearch(arr, 60);
console.log(`索引：${result}`);  // 输出：5

const result2 = interpolationSearch(arr, 85);
console.log(`索引：${result2}`);  // 输出：-1 (不存在)
// 插值查找
func interpolationSearch(arr []int, target int) int {
    left, right := 0, len(arr)-1

    for left <= right && arr[left] <= target && target <= arr[right] {
        if left == right {
            if arr[left] == target {
                return left
            }
            return -1
        }

        // 自适应计算 mid 位置
        mid := left + (target-arr[left])*(right-left)/(arr[right]-arr[left])

        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

// 插值查找 - 递归版本
func interpolationSearchRecursive(arr []int, target, left, right int) int {
    if left > right || target < arr[left] || target > arr[right] {
        return -1
    }

    if left == right {
        if arr[left] == target {
            return left
        }
        return -1
    }

    // 自适应计算 mid 位置
    mid := left + (target-arr[left])*(right-left)/(arr[right]-arr[left])

    if arr[mid] == target {
        return mid
    } else if arr[mid] < target {
        return interpolationSearchRecursive(arr, target, mid+1, right)
    } else {
        return interpolationSearchRecursive(arr, target, left, mid-1)
    }
}

// 使用示例
func main() {
    arr := []int{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
    result := interpolationSearch(arr, 60)
    fmt.Printf("索引：%d\n", result)  // 输出：5

    result = interpolationSearch(arr, 85)
    fmt.Printf("索引：%d\n", result)  // 输出：-1 (不存在)
}

高级算法

🔀 拓扑排序 (Topological Sort)

对有向无环图 (DAG) 的顶点进行线性排序，使得对于每条有向边 (u,v)，顶点 u 在排序中都在顶点 v 之前。常用于任务调度、课程安排、依赖解析等场景。

⭐ 难度：进阶 📦 空间：O(V) ⚡ 时间：O(V+E)
实现方法
  • Kahn 算法 - 基于入度的 BFS 方法，不断移除入度为 0 的节点
  • DFS 方法 - 深度优先搜索，逆序记录完成时间
查看代码示例 
# 拓扑排序 - Kahn 算法 (BFS)
from collections import deque, defaultdict

def topological_sort_kahn(num_nodes, edges):
    """
    Kahn 算法 - 基于入度的 BFS 方法
    num_nodes: 节点数量
    edges: 边列表 [(from, to), ...]
    """
    # 构建邻接表和入度数组
    graph = defaultdict(list)
    in_degree = [0] * num_nodes
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # 初始化队列（入度为 0 的节点）
    queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 检查是否有环
    if len(result) != num_nodes:
        return []  # 存在环，无法拓扑排序
    
    return result

# 拓扑排序 - DFS 方法
def topological_sort_dfs(num_nodes, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
    
    visited = [False] * num_nodes
    result = []
    
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        result.append(node)  # 后序遍历
    
    for i in range(num_nodes):
        if not visited[i]:
            dfs(i)
    
    return result[::-1]  # 逆序

# 测试 - 课程安排问题
# 0 → 1 → 3
# ↓   ↓
# 2 → 4
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4)]
print("Kahn 算法:", topological_sort_kahn(5, edges))
print("DFS 方法:", topological_sort_dfs(5, edges))
// 拓扑排序 - Kahn 算法 (BFS)
function topologicalSortKahn(numNodes, edges) {
    // 构建邻接表和入度数组
    const graph = new Map();
    const inDegree = new Array(numNodes).fill(0);
    
    for (let i = 0; i < numNodes; i++) {
        graph.set(i, []);
    }
    
    for (const [u, v] of edges) {
        graph.get(u).push(v);
        inDegree[v]++;
    }
    
    // 初始化队列（入度为 0 的节点）
    const queue = [];
    for (let i = 0; i < numNodes; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    const result = [];
    
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);
        
        for (const neighbor of graph.get(node)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    // 检查是否有环
    if (result.length !== numNodes) {
        return []; // 存在环
    }
    
    return result;
}

// 拓扑排序 - DFS 方法
function topologicalSortDfs(numNodes, edges) {
    const graph = new Map();
    for (let i = 0; i < numNodes; i++) {
        graph.set(i, []);
    }
    for (const [u, v] of edges) {
        graph.get(u).push(v);
    }
    
    const visited = new Set();
    const result = [];
    
    function dfs(node) {
        visited.add(node);
        for (const neighbor of graph.get(node)) {
            if (!visited.has(neighbor)) {
                dfs(neighbor);
            }
        }
        result.push(node); // 后序遍历
    }
    
    for (let i = 0; i < numNodes; i++) {
        if (!visited.has(i)) {
            dfs(i);
        }
    }
    
    return result.reverse(); // 逆序
}

// 测试 - 课程安排问题
const edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 4]];
console.log("Kahn 算法:", topologicalSortKahn(5, edges));
console.log("DFS 方法:", topologicalSortDfs(5, edges));
package main

import "fmt"

// 拓扑排序 - Kahn 算法 (BFS)
func topologicalSortKahn(numNodes int, edges [][]int) []int {
    // 构建邻接表和入度数组
    graph := make(map[int][]int)
    inDegree := make([]int, numNodes)
    
    for i := 0; i < numNodes; i++ {
        graph[i] = []int{}
    }
    
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        inDegree[v]++
    }
    
    // 初始化队列（入度为 0 的节点）
    queue := []int{}
    for i := 0; i < numNodes; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }
    
    result := []int{}
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    
    // 检查是否有环
    if len(result) != numNodes {
        return []int{} // 存在环
    }
    
    return result
}

// 拓扑排序 - DFS 方法
func topologicalSortDfs(numNodes int, edges [][]int) []int {
    graph := make(map[int][]int)
    for i := 0; i < numNodes; i++ {
        graph[i] = []int{}
    }
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
    }
    
    visited := make([]bool, numNodes)
    result := []int{}
    
    var dfs func(int)
    dfs = func(node int) {
        visited[node] = true
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
        result = append(result, node)
    }
    
    for i := 0; i < numNodes; i++ {
        if !visited[i] {
            dfs(i)
        }
    }
    
    // 逆序
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    
    return result
}

func main() {
    edges := [][]int{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}}
    fmt.Println("Kahn 算法:", topologicalSortKahn(5, edges))
    fmt.Println("DFS 方法:", topologicalSortDfs(5, edges))
}

🔗 并查集 (Union-Find)

用于处理不相交集合的合并与查询问题的高效数据结构。支持两种操作：合并两个集合、查询元素所属集合。常用于连通分量、最小生成树、循环检测等场景。

⭐ 难度：进阶 📦 空间：O(n) ⚡ 时间：O(α(n))*
优化技术
  • 路径压缩 - 查找时将路径上所有节点直接连接到根节点
  • 按秩合并 - 合并时将小树合并到大树上，保持树的平衡
  • *α(n) 为反阿克曼函数，增长极慢，可视为常数时间
查看代码示例 
# 并查集 (Union-Find) 实现
class UnionFind:
    def __init__(self, n):
        """初始化并查集"""
        self.parent = list(range(n))
        self.rank = [0] * n  # 秩（树的近似高度）
        self.count = n  # 连通分量数量
    
    def find(self, x):
        """查找 x 的根节点（带路径压缩）"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        """合并 x 和 y 所在的集合（按秩合并）"""
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX == rootY:
            return False  # 已在同一集合
        
        # 按秩合并
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        
        self.count -= 1
        return True
    
    def connected(self, x, y):
        """判断 x 和 y 是否连通"""
        return self.find(x) == self.find(y)

# 应用 1: 检测图中是否有环
def has_cycle(num_nodes, edges):
    uf = UnionFind(num_nodes)
    for u, v in edges:
        if not uf.union(u, v):
            return True  # 已经连通，形成环
    return False

# 应用 2: 计算连通分量数量
def count_components(num_nodes, edges):
    uf = UnionFind(num_nodes)
    for u, v in edges:
        uf.union(u, v)
    return uf.count

# 测试
edges = [(0, 1), (2, 3), (1, 3)]
print("有环:", has_cycle(4, edges))  # False
print("连通分量:", count_components(4, edges))  # 1

# 测试 - 有环的情况
edges_with_cycle = [(0, 1), (1, 2), (2, 0)]
print("有环:", has_cycle(3, edges_with_cycle))  # True
// 并查集 (Union-Find) 实现
class UnionFind {
    constructor(n) {
        this.parent = new Array(n);
        this.rank = new Array(n).fill(0);
        this.count = n; // 连通分量数量
        
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }
    
    find(x) {
        // 查找 x 的根节点（带路径压缩）
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]); // 路径压缩
        }
        return this.parent[x];
    }
    
    union(x, y) {
        // 合并 x 和 y 所在的集合（按秩合并）
        const rootX = this.find(x);
        const rootY = this.find(y);
        
        if (rootX === rootY) {
            return false; // 已在同一集合
        }
        
        // 按秩合并
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        
        this.count--;
        return true;
    }
    
    connected(x, y) {
        // 判断 x 和 y 是否连通
        return this.find(x) === this.find(y);
    }
}

// 应用 1: 检测图中是否有环
function hasCycle(numNodes, edges) {
    const uf = new UnionFind(numNodes);
    for (const [u, v] of edges) {
        if (!uf.union(u, v)) {
            return true; // 已经连通，形成环
        }
    }
    return false;
}

// 应用 2: 计算连通分量数量
function countComponents(numNodes, edges) {
    const uf = new UnionFind(numNodes);
    for (const [u, v] of edges) {
        uf.union(u, v);
    }
    return uf.count;
}

// 测试
const edges = [[0, 1], [2, 3], [1, 3]];
console.log("有环:", hasCycle(4, edges)); // false
console.log("连通分量:", countComponents(4, edges)); // 1

// 测试 - 有环的情况
const edgesWithCycle = [[0, 1], [1, 2], [2, 0]];
console.log("有环:", hasCycle(3, edgesWithCycle)); // true
package main

import "fmt"

// 并查集 (Union-Find) 实现
type UnionFind struct {
    parent []int
    rank   []int
    count  int // 连通分量数量
}

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
    }
    return &UnionFind{
        parent: parent,
        rank:   rank,
        count:  n,
    }
}

func (uf *UnionFind) Find(x int) int {
    // 查找 x 的根节点（带路径压缩）
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x]) // 路径压缩
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
    // 合并 x 和 y 所在的集合（按秩合并）
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    
    if rootX == rootY {
        return false // 已在同一集合
    }
    
    // 按秩合并
    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
    
    uf.count--
    return true
}

func (uf *UnionFind) Connected(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}

// 应用 1: 检测图中是否有环
func hasCycle(numNodes int, edges [][]int) bool {
    uf := NewUnionFind(numNodes)
    for _, edge := range edges {
        if !uf.Union(edge[0], edge[1]) {
            return true // 已经连通，形成环
        }
    }
    return false
}

// 应用 2: 计算连通分量数量
func countComponents(numNodes int, edges [][]int) int {
    uf := NewUnionFind(numNodes)
    for _, edge := range edges {
        uf.Union(edge[0], edge[1])
    }
    return uf.count
}

func main() {
    edges := [][]int{{0, 1}, {2, 3}, {1, 3}}
    fmt.Println("有环:", hasCycle(4, edges)) // false
    fmt.Println("连通分量:", countComponents(4, edges)) // 1
    
    // 测试 - 有环的情况
    edgesWithCycle := [][]int{{0, 1}, {1, 2}, {2, 0}}
    fmt.Println("有环:", hasCycle(3, edgesWithCycle)) // true
}

查找算法对比

📦 无序数据
顺序查找 O(n)
哈希表 O(1)
📊 有序数据
二分查找 O(log n)
插值查找 O(log log n)
树形查找 O(log n)
🔗 特殊结构
双指针 O(n)
BFS/DFS O(V+E)