二分查找取上界还是下界

二分查找是一种基本的算法，在许多场景下都有着广泛的应用。在实际使用中，我们经常需要查找某个元素在一个有序的数组或者链表中的位置。而二分查找就是一种高效的实现方式。但是，在二分查找中，取上界还是下界常常会让人产生困惑。这篇文章将从多个角度分析这个问题，为大家提供一些启示。

一、二分查找的基本思想

二分查找是一种基于比较的搜索算法，它的基本思想是将中间位置的元素与目标元素进行比较，根据比较结果来决定目标元素可能出现的区间。在每一次比较后，需要根据目标元素可能出现的区间来调整搜索的范围，最后直至找到目标元素为止。由于每次比较会将搜索范围缩小一半，因此二分查找的时间复杂度是 O(log n)。

二、二分查找的变体

在实践中，我们常常需要进行一些变体的二分查找。例如，对于一个有序数组，我们需要查找第一个等于目标元素的位置，或者最后一个小于等于目标元素的位置等。对于这些变体问题，我们需要改变二分查找的判断条件，从而不断缩小目标元素可能出现的区间。

三、取上界还是下界

对于某些变体问题，需要寻找目标元素可能出现的上界或下界。在这种情况下，选择用二分查找来寻找目标元素的位置，就需要在每次比较之后，根据目标元素可能出现的上界或下界来决定调整搜索的范围，而不是简单的将搜索范围缩小一半。

那么，取上界还是下界呢？这个问题的答案并不是唯一的，需要结合具体的问题来进行选择。

（1）取下界

对于需要寻找目标元素可能出现的下界的问题，我们选择取下界。例如，在一个有序数组中，需要查找第一个等于目标元素的位置，或者最后一个小于目标元素的位置等。这种情况下，如果取上界，可能会得出错误的结果。因为如果目标元素不存在于数组中，取上界会返回目标元素可能出现的位置，这显然是不正确的。而如果取下界，我们可以得到目标元素第一次出现的位置，这是正确的。

（2）取上界

对于需要寻找目标元素可能出现的上界的问题，我们选择取上界。例如，在一个有序数组中，需要查找最后一个小于等于目标元素的位置，或者第一个大于目标元素的位置等。这种情况下，如果取下界，可能会使得得到的结果偏大。因为如果目标元素不存在于数组中，取下界会返回目标元素可能出现的位置，这显然是不正确的。而如果取上界，我们可以得到目标元素第一次比较向左偏移一位的位置，这是正确的。

四、小结

综上所述，二分查找是一种应用广泛的算法，在实际使用中需要根据具体问题来选择取上界还是下界。对于需要寻找目标元素可能出现的下界的问题，我们选择取下界；对于需要寻找目标元素可能出现的上界的问题，我们选择取上界。