1 算法题 ：使用二分查找算法在有序数组中查找指定元素
1.1 题目含义
给定一个升序排列的整数数组 nums 和一个目标值 target，写一个函数来搜索 nums 中的 target，如果目标值存在于数组中，则返回它的索引；否则返回 -1。你必须使用二分查找算法来解决这个问题。
二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
1.2 示例
示例 1:
输入：
- nums = [-1, 0, 3, 5, 9, 12]
- target = 9
输出：
- 4
说明：
- 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。否则，根据比较结果递归地在左半部分或右半部分继续查找。递归调用会一直进行下去，直到找到目标值或搜索范围为空。
4 测试用例
以下是针对上面算法的测试用例，基本覆盖了各种情况：
（1）基础测试用例
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 9
输出：4
说明：目标值 9 存在于数组中，位于索引 4 的位置。
（2）目标值不存在于数组中
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 2
输出：-1
说明：目标值 2 不存在于数组中。
（3）目标值位于数组开头
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 -1
输出：0
说明：目标值 -1 位于数组的开头，即索引 0 的位置。
（4）目标值位于数组末尾
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 12
输出：5
说明：目标值 12 位于数组的末尾，即索引 5 的位置。
（5）目标值位于数组中间
输入：数组 [-1, 0, 3, 5, 9, 12]，目标值 3
输出：2
说明：目标值 3 位于数组的中间位置，即索引 2 的位置。
（6）空数组
输入：数组 []，目标值 9
输出：-1
说明：空数组不包含任何元素，因此无法找到目标值。
（7）数组只有一个元素
输入：数组 [9]，目标值 9
输出：0
说明：数组只有一个元素，且该元素就是目标值，位于索引 0 的位置。
（8）数组中存在多个相同的目标值
输入：数组 [1, 2, 3, 3, 4, 5]，目标值 3
输出：2 或 3
说明：数组中存在多个目标值 3，返回任意一个目标值的索引都是正确的。这里可以返回 2 或 3。
