突破编程_C++_查找算法（二分查找）

1 算法题：使用二分查找算法在有序数组中查找指定元素

1.1 题目含义

给定一个升序排列的整数数组 nums 和一个目标值 target，写一个函数来搜索 nums 中的 target，如果目标值存在于数组中，则返回它的索引；否则返回 -1。你必须使用二分查找算法来解决这个问题。

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

1.2 示例

示例 1:
输入：

nums = [-1, 0, 3, 5, 9, 12]
target = 9

输出：

说明：

9 存在于 nums 中，且其索引为 4。

示例 2:
输入：

nums = [-1, 0, 3, 5, 9, 12]
target = 2

输出：

-1

说明：

2 不存在于 nums 中，返回 -1。

示例 3:
输入：

nums = []
target = 0

输出：

-1

说明：

nums 为空，0 不存在于 nums 中，返回 -1。

2 解题思路

2.1 循环遍历实现

（1）初始化指针：

设定三个指针，start 指向数组的开始位置，end 指向数组的结束位置，mid 用于计算当前查找区间的中间位置。

（2）计算中间位置：

根据 start 和 end 的位置，计算出当前查找区间的中间位置 mid。这里要注意防止整数溢出，所以可以使用 (start + end) / 2 的方式来计算。

（3）比较与目标值：

将 mid 位置的元素与目标值进行比较。

（4）调整查找区间：

如果 mid 位置的元素等于目标值，则查找成功，直接返回 mid。
如果 mid 位置的元素大于目标值，说明目标值（如果存在）只可能出现在 mid 的左侧，因此更新 end 为 mid - 1。
如果 mid 位置的元素小于目标值，说明目标值（如果存在）只可能出现在 mid 的右侧，因此更新 start 为 mid + 1。

（5）循环判断：

重复步骤 2 至步骤 4，直到 start 大于 end，这意味着整个查找区间已经被遍历完，且没有找到目标值。

（6）返回结果：

如果循环结束仍然没有找到目标值，则返回 -1 表示查找失败。

2.2 递归实现

使用递归实现二分查找的解题思路如下：

首先，需要明确递归的基本思想：将问题分解为更小的子问题，直到子问题可以直接解决。在二分查找中，每次都将搜索范围划分为两部分，并递归地在其中一部分中继续查找，直到找到目标值或确定目标值不存在。

（1）定义递归函数：

定义一个递归函数，该函数接收一个有序数组、目标值、当前搜索范围的起始位置 start 和结束位置 end 作为参数。

（2）递归终止条件：

当 start 大于 end 时，表示当前搜索范围为空，即目标值不在数组中，递归终止，返回 -1。

（3）计算中间位置：

在递归函数中，计算当前搜索范围的中间位置 mid。

（4）比较与目标值：

将 mid 位置的元素与目标值进行比较。

（5）递归调用：

如果 mid 位置的元素等于目标值，则递归终止，返回 mid。
如果 mid 位置的元素大于目标值，说明目标值（如果存在）只可能出现在 mid 的左侧，因此递归调用函数，传入新的搜索范围（start，mid - 1）。
如果 mid 位置的元素小于目标值，说明目标值（如果存在）只可能出现在 mid 的右侧，因此递归调用函数，传入新的搜索范围（mid + 1，end）。

（6）返回结果：

递归调用的结果即为最终的查找结果，将其返回。

这个递归过程会一直进行下去，直到找到目标值或确定目标值不在数组中。递归实现方式使得代码更加简洁和清晰，但需要注意递归深度的问题，避免因为递归过深而导致栈溢出。在实际应用中，如果数组规模很大，建议使用循环遍历实现来避免这个问题。

3 算法实现代码

3.1 循环遍历实现

如下为算法实现代码：

#include <iostream>  
#include <string>  
#include <vector>  class Solution
{
public:int binarySearch(std::vector<int>& nums, int target) {int start = 0;int end = nums.size() - 1;while (start <= end) {int mid = start + (end - start) / 2; // 防止溢出  if (nums[mid] == target) {// 找到目标值，返回其索引  return mid;}else if (nums[mid] < target) {// 目标值在mid右侧，更新start  start = mid + 1;}else {// 目标值在mid左侧，更新end  end = mid - 1;}}// 没有找到目标值  return -1;}
};

这段代码中定义了一个名为 binarySearch 的成员函数，它接受一个整数向量 nums 和一个目标值 target 作为参数。函数内部使用 start 和 end 变量来追踪当前搜索范围的左右边界，并通过计算中间位置 mid 来确定接下来搜索哪一部分。根据 mid 位置的元素与目标值的比较结果，更新 start 或 end 的值来缩小搜索范围。当 start 大于 end 时，表示搜索区间已被遍历完，此时返回 -1 表示未找到目标值。如果找到目标值，则返回其索引。

调用上面的算法，并得到输出：

int main() 
{Solution s;std::vector<int> nums = { -1, 0, 3, 5, 9, 12 };int target = 9;int result = s.binarySearch(nums, target);if (result != -1) {std::cout << "Target found at index: " << result << std::endl;}else {std::cout << "Target not found in the array." << std::endl;}return 0;
}

上面代码的输出为：

Target found at index: 4

3.2 递归实现

如下为算法实现代码：

#include <iostream>  
#include <string>  
#include <vector>  class Solution
{
public:int binarySearch(std::vector<int>& nums, int target) {		return binarySearchRecursive(nums, target, 0, nums.size() - 1);}private:int binarySearchRecursive(const std::vector<int>& nums, int target, int start, int end) {// 递归终止条件  if (start > end) {return -1; // 目标值不在数组中  }int mid = start + (end - start) / 2; // 防止溢出  // 检查是否找到目标值  if (nums[mid] == target) {return mid;}// 递归调用：目标值在左半部分  if (nums[mid] > target) {return binarySearchRecursive(nums, target, start, mid - 1);}// 递归调用：目标值在右半部分  return binarySearchRecursive(nums, target, mid + 1, end);}
};

这段代码中定义了一个名为 binarySearchRecursive 的私有递归成员函数，它接受一个整数向量 nums、一个目标值 target、以及当前搜索范围的起始位置 start 和结束位置 end 作为参数。
函数内部首先检查递归终止条件，即 start 是否大于 end，如果是，则返回 -1 表示未找到目标值。接着，计算中间位置 mid，然后与目标值进行比较。如果 mid 位置的元素等于目标值，则直接返回 mid。否则，根据比较结果递归地在左半部分或右半部分继续查找。递归调用会一直进行下去，直到找到目标值或搜索范围为空。