使用二分搜索在Java中查找上限和下限（处理升序和降序数组）
原文英文，约900词，阅读约需4分钟。
📝
内容提要
给定排序数组和目标值，实现两个函数找到目标的上限和下限。使用二分搜索高效找到上限和下限。时间复杂度为O(log n)。
🔎
延伸解读
升序与降序数组的二分搜索差异
文章指出，二分搜索在升序和降序数组中的指针移动逻辑相反。对于升序数组，当目标小于中间元素时，需要移动结束指针；而在降序数组中，则移动开始指针。这种差异要求代码中先判断数组顺序，再调整搜索方向。理解这一点是编写通用二分搜索的关键，避免因顺序假设错误导致查找失败。
目标不存在时的返回值处理
当目标值不在数组中时，上限函数返回arr[start]，下限函数返回arr[end]。这是因为循环结束时，start指向大于等于目标的最小元素，end指向小于等于目标的最大元素。这种处理方式确保了即使目标缺失，也能正确找到边界值。读者需注意，返回前应检查索引是否越界，但文章未提及此风险。
时间复杂度与适用场景
文章强调二分搜索的时间复杂度为O(log n)，适合处理大规模有序数组。通过一次遍历同时确定数组顺序并执行搜索，效率较高。但该方法仅适用于已排序数组，若数组无序则需先排序，增加O(n log n)开销。在编程面试和竞赛中，掌握这种通用解法能提升解题速度。
❓
Q&A
如何在Java中实现查找目标值的上限和下限？
可以通过实现两个函数，分别使用二分搜索来查找目标值的上限和下限，时间复杂度为O(log n)。
什么是目标值的上限和下限？
上限是大于或等于目标的最小元素，下限是小于或等于目标的最大元素。
如何判断数组是升序还是降序？
通过比较数组的第一个元素和最后一个元素，如果第一个元素小于最后一个元素，则为升序，否则为降序。
在升序数组中，如何调整指针以找到上限？
如果目标小于中间元素，则移动结束指针；否则，移动开始指针。
如果目标值未找到，如何返回上限和下限？
上限函数返回arr[start]，下限函数返回arr[end]。
为什么掌握二分搜索对编程面试重要？
掌握二分搜索问题有助于提高编程面试和竞争编程能力，因为它是高效解决问题的常用方法。
🏷️
