"这篇博客主要总结了二分查找算法在处理数组问题时的模板应用，包括查找目标值在有序数组中的位置、左侧边界和右侧边界。"
二分查找是一种高效的搜索算法，适用于已排序的数组。它的核心思想是通过每次迭代缩小搜索范围，将问题规模减半，从而达到快速定位目标值的目的。以下是三种常见的二分查找模板：
1. **查找目标值在有序数组中的位置**
这种情况是经典的二分查找，找到目标值所在的位置并返回。如果目标值不存在于数组中，则返回-1。模板代码如下：
```java
public int binarySearch(int[] nums, int target) {
if (nums.length <= 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
// 找到目标值，直接返回
return mid;
}
}
// 目标值不存在，返回-1
return -1;
}
```
2. **查找目标值在有序数组中的左侧边界**
当需要找到目标值左侧的第一个比它大的元素时，我们需要稍微修改二分查找的逻辑。模板代码如下：
```java
public int leftBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 返回左侧边界，如果找不到，返回0
return left;
}
```
3. **查找目标值在有序数组中的右侧边界**
类似地，找到目标值右侧的第一个比它小的元素，我们需要再次调整二分查找的结束条件。模板代码如下：
```java
public int rightBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 返回右侧边界，如果找不到，返回原数组长度
return left;
}
```
这些模板适用于大多数基于二分查找的数组问题，但要注意，它们都假设输入数组是有序的。在实际应用中，还需要考虑数组可能包含重复元素的情况，以及对数组无序时的处理策略。对于无序数组，可以先进行排序，但这会增加额外的时间复杂度。在某些特定问题中，可能需要结合其他数据结构或算法来优化解决方案。
二分查找的效率高，时间复杂度为O(logn)，但前提是数组必须预先排序。在算法面试或编程挑战中，熟练掌握二分查找及其变体，能够有效地解决很多与数组相关的搜索问题。
我的内容管理
展开
