Leetcode_二分查找_0704

May 07, 2024

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 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

解题方法

首先，我们可以考虑使用二分查找算法来解决这个问题。二分查找算法是针对已排序数组的搜索算法，它每次将查找范围缩小一半，从而实现对数级的查找效率。这里是实现二分查找的步骤：

• 1.初始化两个指针，一个指向数组的开始（low），一个指向数组的结束（high）。
• 2.在 low <= high 的条件下，找到中间元素的索引 mid。
• 3.比较中间元素与目标值 target：
• 4.如果中间元素等于 target，则返回 mid。
• 5.如果中间元素小于 target，则将 low 设置为 mid + 1。
• 6.如果中间元素大于 target，则将 high 设置为 mid - 1。
• 7.如果循环结束后没有找到目标值，返回 -1

c++代码实现

二分查找法

#incldeun <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;  // 使用 (low + high) / 2 可能会溢出
        if (nums[mid] == target) {
            return mid; //如果中间元素正好是目标值，返回其索引。
        } else if (nums[mid] < target) {
            low = mid + 1; //如果中间元素小于目标值，调整 low 指针到 mid + 1，即忽略左半部分。
        } else {
            high = mid - 1; //如果中间元素大于目标值，调整 high 指针到 mid - 1，即忽略右半部分。
        }
    }
    return -1;  // 如果未找到目标值
}
int main() {
    // 示例
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int target = 4;
    int result = binarySearch(nums, target);
    if (result != -1) {
        std::cout << "Found target at index: " << result << std::endl;
    } else {
        std::cout << "Target not found." << std::endl;
    }
    return 0;
}

//const std::vector& nums：使用常量引用传递数组是为了防止数组在传递过程中被复制，从而提高效率。 //同时，使用 const 关键字确保函数不会修改数组内容

二分查找法

二分查找法是一种在有序数组中查找特定元素的高效算法。其基本思想是通过不断将搜索范围缩小一半，快速定位目标元素。二分查找的时间复杂度是 𝑂(log𝑛)，其中 n 是数组的长度。

工作原理

• 1.初始化指针： 设置两个指针，low 指向数组的开始，high 指向数组的结束。

• 2.中间元素比较： 计算中间位置的索引 mid 为 (low + high) / 2。

  比较中间位置的元素与目标值:

  **如果相等，说明已找到目标值，返回索引 mid。**
  **如果中间元素小于目标值，则说明目标值在中间元素的右侧，将 low 设置为 mid + 1。**
  **如果中间元素大于目标值，则说明目标值在中间元素的左侧，将 high 设置为 mid - 1。**
  

• 3.重复查找： 在调整 low 和 high 后，重复上述查找过程。 如果 low 超过 high，说明整个数组已经被搜索完毕而没有找到目标值，返回 -1。