# 查找算法

## 目录
- [顺序查找](#顺序查找)
- [二分查找](#二分查找)
- [哈希查找](#哈希查找)
- [算法复杂度分析](#算法复杂度分析)
- [面试常见问题](#面试常见问题)

---

## 顺序查找

### 算法实现

```java
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}
```

### 复杂度

```java
// 时间复杂度：O(n)
// 空间复杂度：O(1)
```

---

## 二分查找

### 算法实现

```java
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 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;
}
```

### 复杂度

```java
// 时间复杂度：O(log n)
// 空间复杂度：O(1)
// 要求：数组必须有序
```

---

## 哈希查找

### 算法实现

```java
// 使用 HashMap
Map<Integer, Integer> map = new HashMap<>();
map.put(1, 10);
map.put(2, 20);

int value = map.get(1); // O(1)
```

### 复杂度

```java
// 时间复杂度：平均 O(1)，最坏 O(n)
// 空间复杂度：O(n)
```

---

## 算法复杂度分析

### 对比表

| 算法 | 时间复杂度 | 空间复杂度 | 要求 |
|------|-----------|-----------|------|
| 顺序查找 | O(n) | O(1) | 无 |
| 二分查找 | O(log n) | O(1) | 有序 |
| 哈希查找 | O(1) | O(n) | 无 |

---

## 面试常见问题

### Q1: 二分查找的条件？

**答案：**
- 数组必须有序
- 时间复杂度 O(log n)

### Q2: 哈希查找的特点？

**答案：**
- 平均时间复杂度 O(1)
- 需要额外空间
- 可能哈希冲突

---

*最后更新：2024年*
