二分查找算法模板详细解析

"这篇博客主要总结了二分查找算法在处理数组问题时的模板应用，包括查找目标值在有序数组中的位置、左侧边界和右侧边界。" 二分查找是一种高效的搜索算法，适用于已排序的数组。它的核心思想是通过每次迭代缩小搜索范围，将问题规模减半，从而达到快速定位目标值的目的。以下是三种常见的二分查找模板： 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)，但前提是数组必须预先排序。在算法面试或编程挑战中，熟练掌握二分查找及其变体，能够有效地解决很多与数组相关的搜索问题。