搜索算法

什么是搜索算法？

搜索算法用于在数据集合中查找特定元素或信息。常见的搜索算法包括线性搜索、二分搜索、深度优先搜索、广度优先搜索等。

在有序数组中，通过不断将搜索范围减半来快速定位目标元素。

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

// 测试
const sortedArr = [1, 3, 5, 7, 9, 11, 13, 15, 17];
console.log(binarySearch(sortedArr, 7)); // 3
console.log(binarySearch(sortedArr, 4)); // -1

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # 未找到

# 测试
sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
print(binary_search(sorted_arr, 7))  # 3
print(binary_search(sorted_arr, 4))  # -1

package main

import "fmt"

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    
    for left <= right {
        mid := (left + right) / 2
        
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return -1  // 未找到
}

func main() {
    sortedArr := []int{1, 3, 5, 7, 9, 11, 13, 15, 17}
    fmt.Println(binarySearch(sortedArr, 7)) // 3
    fmt.Println(binarySearch(sortedArr, 4)) // -1
}

从起点开始，尽可能深地探索图的每个分支，直到无法继续为止，然后回溯。

// 图的邻接表表示
const graph = {
    A: ['B', 'C'],
    B: ['D', 'E'],
    C: ['F'],
    D: [],
    E: ['F'],
    F: []
};

function dfs(graph, start) {
    const visited = new Set();
    const result = [];
    
    function dfsHelper(node) {
        visited.add(node);
        result.push(node);
        
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                dfsHelper(neighbor);
            }
        }
    }
    
    dfsHelper(start);
    return result;
}

// 测试
console.log(dfs(graph, 'A')); // ['A', 'B', 'D', 'E', 'F', 'C']

# 图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def dfs(graph, start):
    visited = set()
    result = []
    
    def dfs_helper(node):
        visited.add(node)
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs_helper(neighbor)
    
    dfs_helper(start)
    return result

# 测试
print(dfs(graph, 'A'))  # ['A', 'B', 'D', 'E', 'F', 'C']

package main

import "fmt"

func dfs(graph map[string][]string, start string) []string {
    visited := make(map[string]bool)
    result := []string{}

    var dfsHelper func(node string)
    dfsHelper = func(node string) {
        visited[node] = true
        result = append(result, node)

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

    dfsHelper(start)
    return result
}

func main() {
    graph := map[string][]string{
        "A": {"B", "C"},
        "B": {"D", "E"},
        "C": {"F"},
        "D": {},
        "E": {"F"},
        "F": {},
    }

    result := dfs(graph, "A")
    fmt.Println(result) // [A B D E F C]
}

从起点开始，先访问所有相邻节点，然后再依次访问这些节点的相邻节点，逐层向外扩展。

// 使用相同的图结构
function bfs(graph, start) {
    const visited = new Set([start]);
    const queue = [start];
    const result = [];
    
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);
        
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    
    return result;
}

// 测试
console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E', 'F']

# 使用相同的图结构
def bfs(graph, start):
    visited = {start}
    queue = [start]
    result = []
    
    while queue:
        node = queue.pop(0)
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# 测试
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

package main

import "fmt"

func bfs(graph map[string][]string, start string) []string {
    visited := make(map[string]bool)
    visited[start] = true
    queue := []string{start}
    result := []string{}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)

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

    return result
}

func main() {
    graph := map[string][]string{
        "A": {"B", "C"},
        "B": {"D", "E"},
        "C": {"F"},
        "D": {},
        "E": {"F"},
        "F": {},
    }

    result := bfs(graph, "A")
    fmt.Println(result) // [A B C D E F]
}

特性	DFS	BFS
数据结构	栈	队列
路径选择	优先深度	优先广度
最短路径	不保证	保证
内存使用	较少	较多

熟练掌握二分查找，这是最常用的搜索算法
理解DFS和BFS的适用场景
学习如何处理图和树的搜索问题
掌握剪枝技巧优化搜索效率

什么是搜索算法？

二分查找

DFS/BFS

线性搜索

二分查找 (Binary Search)

深度优先搜索 (DFS)

广度优先搜索 (BFS)

DFS vs BFS

学习建议