二分查找向下取整

二分查找是一种高效率的查找算法，它将查找的时间复杂度从O(n)降低至O(log n)，因此在工程中得到了广泛应用和推广。然而，二分查找默认的是向上取整，也就是如果查找的目标不在数组中，就返回当前左端点所指向的位置。这种默认行为有时会导致一些问题，比如当我们需要在数据中找到一个坐标等于某个值的位置时，但是无法找到，我们需要将查找的结果向下取整到最靠近目标值的位置上。本文将着重从多个角度分析这个问题，探讨二分查找向下取整的实现方式以及相应的注意事项。

一、简介

二分查找法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半，时间复杂度为O(log n)。

二、二分查找默认的向上取整

可以看以下二分查找的模板：

```

int left = 0, right = nums.length - 1;

while (left <= right) {

int mid = (left + right) / 2;

if (nums[mid] == target) {

// find the target

} else if (nums[mid] < target) {

left = mid + 1;

} else {

right = mid - 1;

}

}

```

这个模板默认的是向上取整，即如果查找的目标不在数组中，就返回当前左端点所指向的位置。比如，在下面这个数组中查找7：

```

int[] nums = {1, 3, 5, 6};

```

通过默认的二分查找，我们会得到mid=2，但是这个2位置上的数字是5，而不是我们需要的7。这个问题的解决方案是，将查找结果向下取整到最靠近目标值的位置上。

三、实现二分查找向下取整

实现二分查找向下取整，我们需要将mid计算方式进行改进。通常我们可以这样写：

```

int mid = left + (right - left) / 2;

```

这样可以避免整数越界的问题，而且会得到当前区间的中间位置。但是这种计算方式默认还是向上取整，因此需要对mid进行调整：

```

mid = left + (right - left + 1) / 2;

```

当区间左右端点相邻时，mid会指向右端点，当然，集合中有x时，mid会指向尽可能靠左的哪一个。这样，当我们在数组中查找7时，我们会得到mid=1，也就是2位置的左边那个位置上，这样就实现了向下取整。

四、二分查找向下取整的注意事项

1.在实现二分查找向下取整时，我们需要注意原有代码对mid的使用。如果mid和其他变量同时使用时，我们需要对使用mid的代码进行相应的调整。

2.二分查找向下取整只是一种特殊情况下的查找方式，具体使用时需要根据问题的实际情况进行判断和调整。

3.在使用二分查找时，我们需要注意区间左右端点的范围，确保不会出现越界的情况。

5、总结

本文从多个角度分析了二分查找向下取整的实现方式以及相应的注意事项，具体实现方法就是对mid进行调整，将mid左移一位(用右移一位亦可)。同时，实现二分查找向下取整时需要注意原有代码对mid的使用和区间左右端点的范围。