L5_05 二分算法

一、二分算法概述

二分算法，也称为二分查找或折半查找，是一种高效的搜索算法。它的核心思想是将有序数组分成两部分，通过比较中间元素与目标值的大小关系，缩小搜索范围，直到找到目标元素或确定目标不存在。

1.1 算法特点

• 时间复杂度：O(log n)
• 空间复杂度：O(1)（迭代实现）或 O(log n)（递归实现）
• 适用条件：必须是有序数组

1.2 基本思想

1. 初始化左右指针：left = 0，right = n - 1
2. 循环直到 left > right：
   • 计算中间位置：mid = left + (right - left) / 2
   • 如果 arr[mid] == target，返回 mid
   • 如果 arr[mid] < target，搜索右半部分：left = mid + 1
   • 如果 arr[mid] > target，搜索左半部分：right = mid - 1
3. 如果循环结束未找到，返回 -1

---

二、二分查找算法

2.1 基本二分查找（迭代实现）

int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int 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;  // 未找到
}

2.2 递归实现

int binarySearchRecursive(const vector<int>& arr, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int 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);
    }
}

---

三、二分答案算法

二分答案算法，也称为二分枚举法，是二分查找的一种扩展应用。它通过二分法在答案范围内搜索最优解。

3.1 适用场景

• 问题的答案在一个有序范围内
• 可以快速判断某个值是否是可行解

3.2 算法框架

int findAnswer(int left, int right) {
    int answer = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (isValid(mid)) {
            answer = mid;
            left = mid + 1;  // 尝试更大的值
        } else {
            right = mid - 1;  // 需要更小的值
        }
    }
    
    return answer;
}

3.3 示例：寻找最大值

bool isValid(int mid) {
    // 判断 mid 是否是可行解
    // 返回 true 表示可行，false 表示不可行
}

---

四、二分查找的变种

4.1 查找第一个等于目标值的元素

int findFirst(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // 继续向左搜索
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

4.2 查找最后一个等于目标值的元素

int findLast(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;  // 继续向右搜索
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

4.3 查找第一个大于等于目标值的元素

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

---

五、二分算法的应用

5.1 在有序数组中查找元素

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    
    int index = binarySearch(arr, target);
    
    if (index != -1) {
        cout << "找到目标元素，索引为: " << index << endl;
    } else {
        cout << "未找到目标元素" << endl;
    }
    
    return 0;
}

5.2 二分答案示例：最大化最小值

bool canPlaceFlowers(const vector<int>& positions, int m, int distance) {
    int count = 1;
    int last = positions[0];
    
    for (size_t i = 1; i < positions.size(); ++i) {
        if (positions[i] - last >= distance) {
            count++;
            last = positions[i];
            if (count >= m) {
                return true;
            }
        }
    }
    
    return count >= m;
}

int maxMinDistance(vector<int>& positions, int m) {
    sort(positions.begin(), positions.end());
    
    int left = 1;
    int right = positions.back() - positions[0];
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (canPlaceFlowers(positions, m, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

---

六、注意事项

1. 数组必须有序：二分查找只适用于有序数组
2. 防止溢出：使用 mid = left + (right - left) / 2 代替 mid = (left + right) / 2
3. 边界处理：注意 left 和 right 的初始值和更新方式
4. 重复元素：考虑数组中有重复元素的情况

---

七、总结

二分算法是一种高效的搜索和优化算法，时间复杂度为 O(log n)。掌握二分查找和二分答案两种形式，能够解决许多算法问题。