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