二分搜索算法例题

二分搜索算法是一种在有序数组中查找特定元素的搜索算法，也叫折半查找算法。其基本思想是将数组中间元素与目标元素作比较，如果中间元素等于目标元素，则返回该元素的索引值；如果中间元素大于目标元素，则在数组的左半部分继续查找；如果中间元素小于目标元素，则在数组的右半部分继续查找。通过不断折半比较，最终可以找到目标元素的索引值或者确定目标元素不存在于数组中。

在实际应用中，二分搜索算法广泛应用于搜索引擎、数据库索引以及各种算法和数据结构的实现。以下是一个例题，通过多个角度分析二分搜索算法的实现过程和应用。

示例题目：

给定一个有序数组 nums ，请你在数组中查找两个数字，使它们的和等于给定的目标值 target。

示例：

输入：nums = [2, 7, 11, 15], target = 9

输出：[1, 2]

解释：因为 nums[1] + nums[2] == 9 ，所以返回 [1, 2] 。

思路分析：

该题目可以采用暴力枚举、哈希表以及二分搜索三种算法解决。这里选择介绍二分搜索算法的解法。

首先，定义一个 left 指针和一个 right 指针，分别指向数组的左右两端。将它们相加，如果和等于目标值 target，直接返回它们的索引；如果和小于目标值 target，则将 left 指针向右移动一位，增大和的值；如果和大于目标值 target，则将 right 指针向左移动一位，减小和的值。不断进行上述操作，直至 left 指针大于 right 指针，说明已经搜索完整个有序数组，但没有找到符合条件的元素，返回空数组。

代码实现：

class Solution {

public:

vector twoSum(vector & nums, int target) {

int left = 0, right = nums.size() - 1;

while (left < right) {

int sum = nums[left] + nums[right];

if (sum == target) {

return {left + 1, right + 1};

} else if (sum < target) {

left += 1;

} else {

right -= 1;

}

}

return {}; // 没有符合条件的元素，返回空数组

}

};

时间复杂度分析：

二分搜索算法的时间复杂度为 O(log n)，其核心思想在于每次削减搜索范围为原来的一半，目标值最终会被二分至数组中且只需要 O(log n)次，因此时间复杂度为 O(log n)。

空间复杂度分析：

二分搜索算法只需要常数级别的空间存储 left 和 right 两个指针，因此空间复杂度为 O(1)。

应用场景：

二分搜索算法常用于查找元素、查找区间、查找边界等问题，其适用于有序数组或部分有序的数组，通过不断折半缩小搜索范围，可以快速查找目标元素。在实际应用中，二分搜索算法广泛应用于搜索引擎、数据库索引以及各种算法和数据结构的实现。