02-搜索算法

💡 核心结论

二分查找

• 前提：有序数组

• 原理：每次排除一半，O(log n)

• 关键：左右边界、while条件、mid计算

• 变种：查找第一个/最后一个、查找范围

• 应用：搜索、求根、最优化问题

深度优先搜索（DFS）

• 策略：一条路走到底，走不通回退

• 实现：递归或栈

• 应用：路径搜索、连通性、拓扑排序

• 复杂度：O(V + E)

广度优先搜索（BFS）

• 策略：逐层搜索，找最短路径

• 实现：队列

• 应用：最短路径、层序遍历

• 复杂度：O(V + E)

DFS vs BFS

特性	DFS	BFS
数据结构	栈/递归	队列
空间	O(h)	O(w)
最短路径	❌	✅
实现	更简洁	需要队列
适用	路径、连通性	最短路径、层序

🔍 二分查找

基本模板

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 left_bound(arr, target):
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

右边界查找

def right_bound(arr, target):
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left - 1

🌲 DFS深度优先

递归实现

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

栈实现

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

🌊 BFS广度优先

队列实现

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        print(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

分层BFS

def bfs_levels(graph, start):
    visited = set([start])
    queue = deque([start])
    level = 0
    
    while queue:
        size = len(queue)
        print(f"Level {level}:")
        
        for _ in range(size):
            node = queue.popleft()
            print(f"  {node}")
            
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        level += 1

📚 LeetCode练习

二分查找

• 704. Binary Search

• 34. Find First and Last Position

• 69. Sqrt(x)

• 33. Search in Rotated Sorted Array

DFS/BFS

• 200. Number of Islands

• 207. Course Schedule

• 133. Clone Graph

• 127. Word Ladder

💻 完整代码实现

Python 实现

"""
二分查找及变种
"""

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 left_bound(arr, target):
    """查找左边界（第一个>=target的位置）"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left


def right_bound(arr, target):
    """查找右边界（最后一个<=target的位置）"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left - 1


def search_range(arr, target):
    """查找target的起始和结束位置"""
    left = left_bound(arr, target)
    right = right_bound(arr, target)
    
    if left >= len(arr) or arr[left] != target:
        return [-1, -1]
    
    return [left, right]


# ========== 应用 ==========

def my_sqrt(x):
    """求平方根（整数部分）"""
    if x < 2:
        return x
    
    left, right = 1, x // 2
    
    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return right


def search_rotated(nums, target):
    """旋转数组中查找"""
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # 判断哪一半是有序的
        if nums[left] <= nums[mid]:
            # 左半有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # 右半有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1


def find_peak_element(nums):
    """找峰值元素"""
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid
    
    return left


def demo():
    """演示二分查找"""
    print("=== 二分查找演示 ===\n")
    
    arr = [1, 2, 2, 2, 3, 4, 5, 5, 6]
    target = 2
    
    print(f"数组: {arr}")
    print(f"目标: {target}\n")
    
    print(f"基本查找: {binary_search(arr, target)}")
    print(f"左边界: {left_bound(arr, target)}")
    print(f"右边界: {right_bound(arr, target)}")
    print(f"查找范围: {search_range(arr, target)}\n")
    
    # 平方根
    x = 8
    print(f"sqrt({x}) = {my_sqrt(x)}\n")
    
    # 旋转数组
    rotated = [4, 5, 6, 7, 0, 1, 2]
    target = 0
    print(f"旋转数组: {rotated}")
    print(f"查找 {target}: {search_rotated(rotated, target)}\n")
    
    # 峰值
    nums = [1, 2, 3, 1]
    print(f"数组: {nums}")
    print(f"峰值索引: {find_peak_element(nums)}")


if __name__ == '__main__':
    demo()

"""
DFS和BFS实现
"""

from collections import deque

# ========== DFS深度优先 ==========

def dfs_recursive(graph, start, visited=None):
    """DFS递归实现"""
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited


def dfs_iterative(graph, start):
    """DFS迭代实现（栈）"""
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            # 逆序添加邻居（保证顺序）
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result


# ========== BFS广度优先 ==========

def bfs(graph, start):
    """BFS实现（队列）"""
    visited = {start}
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result


def bfs_shortest_path(graph, start, end):
    """BFS求最短路径"""
    if start == end:
        return [start]
    
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        node, path = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path
                visited.add(neighbor)
                queue.append((neighbor, new_path))
    
    return None


def bfs_levels(graph, start):
    """BFS分层遍历"""
    visited = {start}
    queue = deque([start])
    levels = []
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node)
            
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        levels.append(current_level)
    
    return levels


# ========== 应用：岛屿数量 ==========

def num_islands(grid):
    """岛屿数量（DFS）"""
    if not grid:
        return 0
    
    m, n = len(grid), len(grid[0])
    count = 0
    
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
            return
        
        grid[i][j] = '0'  # 标记已访问
        
        # 四个方向
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count


# ========== 应用：课程表（拓扑排序） ==========

def can_finish(num_courses, prerequisites):
    """判断能否完成所有课程（检测环）"""
    graph = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)
    
    visited = [0] * num_courses  # 0:未访问 1:访问中 2:已完成
    
    def has_cycle(node):
        if visited[node] == 1:
            return True  # 发现环
        if visited[node] == 2:
            return False
        
        visited[node] = 1
        for neighbor in graph[node]:
            if has_cycle(neighbor):
                return True
        visited[node] = 2
        return False
    
    for i in range(num_courses):
        if visited[i] == 0:
            if has_cycle(i):
                return False
    
    return True


def demo():
    """演示DFS和BFS"""
    print("=== DFS和BFS演示 ===\n")
    
    # 构建图
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    print("图结构:")
    for node, neighbors in graph.items():
        print(f"  {node}: {neighbors}")
    print()
    
    print("DFS遍历（递归）: ", end='')
    dfs_recursive(graph, 'A')
    print("\n")
    
    print("DFS遍历（迭代）:", dfs_iterative(graph, 'A'))
    print("BFS遍历:", bfs(graph, 'A'))
    print()
    
    # 最短路径
    path = bfs_shortest_path(graph, 'A', 'F')
    print(f"从A到F的最短路径: {' -> '.join(path) if path else 'None'}")
    print()
    
    # 分层遍历
    print("BFS分层遍历:")
    levels = bfs_levels(graph, 'A')
    for i, level in enumerate(levels):
        print(f"  Level {i}: {level}")
    print()
    
    # 岛屿数量
    grid = [
        ['1', '1', '0', '0', '0'],
        ['1', '1', '0', '0', '0'],
        ['0', '0', '1', '0', '0'],
        ['0', '0', '0', '1', '1']
    ]
    print("岛屿数量:")
    for row in grid:
        print(f"  {row}")
    # 注意：会修改grid，这里重新创建
    grid_copy = [row[:] for row in grid]
    print(f"岛屿数量: {num_islands(grid_copy)}")


if __name__ == '__main__':
    demo()

C++ 实现

/**
 * 二分查找及变种实现
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 基本二分查找
int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int 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;
}

// 左边界查找
int leftBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

// 右边界查找
int rightBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left - 1;
}

// 平方根
int mySqrt(int x) {
    if (x < 2) return x;
    
    int left = 1, right = x / 2;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long long square = (long long)mid * mid;
        
        if (square == x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return right;
}

// 旋转数组查找
int searchRotated(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        }
        
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

int main() {
    cout << "=== 二分查找演示 ===" << endl << endl;
    
    vector<int> arr = {1, 2, 2, 2, 3, 4, 5, 5, 6};
    int target = 2;
    
    cout << "数组: [";
    for (size_t i = 0; i < arr.size(); i++) {
        cout << arr[i];
        if (i < arr.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    cout << "目标: " << target << endl << endl;
    
    cout << "基本查找: " << binarySearch(arr, target) << endl;
    cout << "左边界: " << leftBound(arr, target) << endl;
    cout << "右边界: " << rightBound(arr, target) << endl << endl;
    
    int x = 8;
    cout << "sqrt(" << x << ") = " << mySqrt(x) << endl << endl;
    
    vector<int> rotated = {4, 5, 6, 7, 0, 1, 2};
    int search_target = 0;
    cout << "旋转数组: [";
    for (size_t i = 0; i < rotated.size(); i++) {
        cout << rotated[i];
        if (i < rotated.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    cout << "查找 " << search_target << ": " << searchRotated(rotated, search_target) << endl;
    
    return 0;
}

/**
 * DFS和BFS实现
 */

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_set>
#include <unordered_map>

using namespace std;

// DFS递归
void dfsRecursive(const unordered_map<int, vector<int>>& graph, 
                  int node, unordered_set<int>& visited) {
    visited.insert(node);
    cout << node << " ";
    
    if (graph.count(node)) {
        for (int neighbor : graph.at(node)) {
            if (!visited.count(neighbor)) {
                dfsRecursive(graph, neighbor, visited);
            }
        }
    }
}

// DFS迭代（栈）
vector<int> dfsIterative(const unordered_map<int, vector<int>>& graph, int start) {
    unordered_set<int> visited;
    stack<int> st;
    vector<int> result;
    
    st.push(start);
    
    while (!st.empty()) {
        int node = st.top();
        st.pop();
        
        if (!visited.count(node)) {
            visited.insert(node);
            result.push_back(node);
            
            if (graph.count(node)) {
                auto neighbors = graph.at(node);
                for (auto it = neighbors.rbegin(); it != neighbors.rend(); ++it) {
                    if (!visited.count(*it)) {
                        st.push(*it);
                    }
                }
            }
        }
    }
    
    return result;
}

// BFS（队列）
vector<int> bfs(const unordered_map<int, vector<int>>& graph, int start) {
    unordered_set<int> visited;
    queue<int> q;
    vector<int> result;
    
    visited.insert(start);
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        
        if (graph.count(node)) {
            for (int neighbor : graph.at(node)) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }
    
    return result;
}

// 岛屿数量
void dfsIsland(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size();
    int n = grid[0].size();
    
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
        return;
    }
    
    grid[i][j] = '0';
    
    dfsIsland(grid, i + 1, j);
    dfsIsland(grid, i - 1, j);
    dfsIsland(grid, i, j + 1);
    dfsIsland(grid, i, j - 1);
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int count = 0;
    int m = grid.size();
    int n = grid[0].size();
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfsIsland(grid, i, j);
            }
        }
    }
    
    return count;
}

int main() {
    cout << "=== DFS和BFS演示 ===" << endl << endl;
    
    // 构建图
    unordered_map<int, vector<int>> graph;
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5};
    graph[3] = {1};
    graph[4] = {1, 5};
    graph[5] = {2, 4};
    
    cout << "图结构:" << endl;
    for (const auto& pair : graph) {
        cout << "  " << pair.first << ": [";
        for (size_t i = 0; i < pair.second.size(); i++) {
            cout << pair.second[i];
            if (i < pair.second.size() - 1) cout << ", ";
        }
        cout << "]" << endl;
    }
    cout << endl;
    
    // DFS
    cout << "DFS遍历（递归）: ";
    unordered_set<int> visited;
    dfsRecursive(graph, 0, visited);
    cout << endl << endl;
    
    cout << "DFS遍历（迭代）: ";
    vector<int> dfs_result = dfsIterative(graph, 0);
    for (int node : dfs_result) {
        cout << node << " ";
    }
    cout << endl << endl;
    
    // BFS
    cout << "BFS遍历: ";
    vector<int> bfs_result = bfs(graph, 0);
    for (int node : bfs_result) {
        cout << node << " ";
    }
    cout << endl << endl;
    
    // 岛屿数量
    cout << "岛屿数量:" << endl;
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    
    for (const auto& row : grid) {
        cout << "  ";
        for (char cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }
    cout << "岛屿数量: " << numIslands(grid) << endl;
    
    return 0;
}