DEV Community
·
使用二分搜索在Java中查找上限和下限（处理升序和降序数组）
💡
原文英文，约900词，阅读约需4分钟。
📝
内容提要
给定排序数组和目标值，实现两个函数找到目标的上限和下限。使用二分搜索高效找到上限和下限。时间复杂度为O(log n)。
🎯
关键要点
- 给定一个排序数组和目标值，需实现两个函数：一个找到目标的上限，另一个找到下限。
- 目标的上限是大于或等于目标的最小元素，下限是小于或等于目标的最大元素。
- 数组可以是升序或降序，使用二分搜索高效找到上限和下限，时间复杂度为O(log n)。
- 在升序数组中，当目标小于中间元素时，移动结束指针；在降序数组中，逻辑相反。
- 如果目标未找到，上限函数返回arr[start]，下限函数返回arr[end]。
- 通过处理升序和降序数组，我们创建了一个通用的解决方案，适用于任何排序数组。
- 掌握二分搜索问题对提高编程面试和竞争编程能力至关重要。
➡️
