leetcode704------二分法查找有序数组中特定的值

news/2025/2/27 3:30:54

目录

一、二分法的基本概念 

二、二分法的基本步骤

三、迭代二分法查找有序数组中的特定值题目

3.1 题目介绍 

3.2 求解思路

3.2.1 情况一：左闭右闭[left, right]

3.2.2 情况二：左闭右开[left, right) 

四、二分法的时间复杂度与空间复杂度

4.1 时间复杂度

4.2 空间复杂度

一、二分法的基本概念 

二分法，也称为折半查找，是一种在有序数组中高效查找特定元素的搜索算法。它的基本思想是通过不断地将搜索区间减半来快速定位目标元素。具体实现是：首先确定搜索区间的中间元素，如果中间元素等于目标值，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

二、二分法的基本步骤

  1. 定义查找的范围：初始时设定查找区间的左右边界，通常用两个指针left和right。
  2. 计算中间位置：mid = (left + right) // 2，即区间的中间索引。
  3. 比较中间元素：
    • 如果array[mid] == target，则找到目标，返回索引。
    • 如果array[mid] < target，则目标在右半部分，更新left = mid + 1。
    • 如果array[mid] > target，则目标在左半部分，更新right = mid - 1。
  4. 重复以上步骤，直到找到目标或者区间为空（left > right）。

三、迭代二分法查找有序数组中的特定值题目

3.1 题目介绍 

题目来源：leetcode第704道题目

题目链接：https://leetcode.cn/problems/binary-search/description/


给定一个 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

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

3.2 求解思路

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。当然也可以左开右闭(left, right]，但是这种不推荐。

3.2.1 情况一：左闭右闭[left, right]

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1。

例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：

伪代码

// 情况1：查找区间在[left,right]
二分法查找(target) // target 表示要查找的目标值
{
   // 一些变量的定义   
   left=0; // 左边界从0开始
   right=nums.size-1; // 右边界为数组的长度-1，nums表示数组

   
   // 开始二分法
   while(left<=right) // 查找区间在[left,right]，因此为<=
   {
      middle = (left+right)/2; // 中间索引
      if(nums[middle]>target) // 条件成立时，说明target在左子区间，此时更新right即可
      {
          right = middle-1; // 为什么是middle-1而不是middle？原因：在if判断语句中条件为nums[middle]>target，已经确保nums[middle]不会等于target，也就是说下标索引为middle的值必然不符合，若为right = middle，那么在下一次while循环的时候遍历的区间即为[left=0,right=middle]，也就是说，程序把本该不属于自己搜索区间的值放在了搜索区间进行搜索，这造成了矛盾。
     
      elif(nums[middle]<target) // 条件成立时，说明target在右子区间，此时更新left即可
      {
         left=middle+1;
      }
      else // nums[middle] == target
      {
          return middle; // 返回中间索引
      } 
   }
return -1; //返回-1，没有找到目标值
   
}

 正式代码【C++版本】

#include<iostream>
#include<vector>
// 二分法查找顺序数组中指定元素
int binary_seperate(std::vector<int> nums, int target){
    // 定义左边界以及右边界
    int left = 0; // 左边界
    int right = nums.size() - 1; // 右边界
    while(left<=right){
        int middle = (left+right)/2;
        if(nums[middle]>target){ // 条件成立，说明target在左子区间，此时需更新right边界
            right = middle - 1; // 这里right不能等于middle，伪代码中有解释
        }
        else if(nums[middle]<target){ // 条件成立，说明target在右子区间，此时需更新 left 边界
            left = middle + 1;
        }
        else{ // nums[middle]==target，找到目标值
            return middle; // 返回目标值所在下标
        }
    }
    return -1; // 如果没有找到，那就返回 -1
}

int main() {
    std::vector<int> nums1{1,2,3,4,7,9,10}; // 定义一个数组
    int found_target=2; // 要查询的值
    int erfen_found = binary_seperate(nums1, found_target);
    std::cout<< "要找的目标值为:"<< found_target <<",其索引所在位置为:"<<erfen_found << std::endl;
    return 0;

}

3.2.2 情况二：左闭右开[left, right) 

伪代码

// 情况2：查找区间在[left,right)
二分法查找(nums,target) // nums表示待查询的数组，target 表示要查找的目标值
{
   // 一些变量的定义   
   left=0; // 左边界从0开始
   right=nums.size; // 此时右边界为数组的长度，这是因为查找区间在[left,right)，right取不到，因此要多加一个，即把“-1”去掉

   
   // 开始二分法
   while(left<right) // 查找区间在[left,right)，因此为<
   {
      middle = (left+right)/2; // 中间索引
      if(nums[middle]>target) // 条件成立时，说明target在左子区间，此时更新right即可
      {
          right = middle; // 为什么是middle？原因：如果right = middle-1，那么下一次搜索空间是[left=0,right=middle-1)，这样就会少搜索了nums[middle-1]这个值。
     
      elif(nums[middle]<target) // 条件成立时，说明target在右子区间，此时更新left即可
      {
         left=middle+1;
      }
      else // nums[middle] == target
      {
          return middle; // 返回中间索引
      } 
   }
return -1; //返回-1，没有找到目标值
   
}

正式代码【C++版本】 

// 情况2： 查找范围为[left,right)，注意，此时不包含right边界值
int binary_seperate(std::vector<int> nums, int target){
    int left = 0;
    int right = nums.size();

    while(left<right){
        int middle = (left+right)/2;
        if(nums[middle]>target){
            right = middle;
        }
        else if(nums[middle]<target){
            left = middle + 1;
        }
        else{ // nums[middle]==target
            return middle; // 找到，返回下标索引
        }
    } 
    return -1; // 没找到，返回-1
}


int main() {
    std::vector<int> nums1{1,2,3,4,7,9,10}; // 定义一个数组
    int found_target=2; // 要查询的值
    int erfen_found = binary_seperate(nums1, found_target);
    std::cout<< "要找的目标值为:"<< found_target <<",其索引所在位置为:"<<erfen_found << std::endl;
    return 0;

}

四、二分法的时间复杂度与空间复杂度

4.1 时间复杂度

  • 时间复杂度为O(log n)，因为每次查找都会将查找区间缩小一半。

解析： 

二分法通过每次将搜索区间分成两半来查找目标元素。假设初始时数组有 n 个元素，二分法每次都会检查中间的元素，并将搜索范围缩小到剩下的一半。这样，随着每一步的进行，搜索区间的大小减少一半，直到搜索区间大小为1。

具体步骤：

  1. 第一次迭代：在 n 个元素中找到中间元素，将搜索区间缩小为 n / 2。
  2. 第二次迭代：再将剩余的 n / 2 个元素分为两半，缩小到 n / 4。
  3. 第三次迭代：继续缩小到 n / 8，以此类推。
  4. 经过 k 次迭代后，剩余的搜索区间大小为：n/(2^k)​
  5. 当剩余的搜索区间只有一个元素时，即：n/(2^k)​=1
  6. 解这个方程，得到：k=log2​n

所以，经过大约 log₂(n) 次迭代，算法将停止，并找到目标元素或确认目标元素不存在。

关于时间复杂度为什么是这个值，请观看视频：https://www.bilibili.com/video/BV1aw411A7uL?spm_id_from=333.788.videopod.sections&vd_source=fb7bfda367c76676e2483b9b60485e57

4.2 空间复杂度

空间复杂度为 O(1)。

  • 只使用了常量额外空间

    • 代码中只使用了几个整数变量：left、right 和 middle。
    • 这些变量的存储空间 不会随着输入数组的大小变化，始终是常量级别的空间需求。

  • 不依赖额外的数据结构

    • 代码没有使用递归，也没有额外分配数组、列表或其他数据结构。
    • 所有计算都在原始数组 nums 上进行，没有额外存储需求。

http://www.niftyadmin.cn/n/5869417.html

相关文章

【STM32】玩转IIC之驱动MPU6050及姿态解算

【STM32】玩转IIC之驱动MPU6050及姿态解算

目录 前言 一.MPU6050模块介绍 1.1MPU6050简介 1.2 MPU6050的引脚定义 1.3MPU6050寄存器解析 二.MPU6050驱动开发 2.1 配置寄存器 2.2对MPU6050寄存器进行读写 2.2.1 写入寄存器 2.2.2读取寄存器 2.3 初始化MPU6050 2.3.1 设置工作模式 2.3.2 配置采样率 2.3.3 启…
阅读更多...
MySQL | MySQL库、表的基本操作

MySQL | MySQL库、表的基本操作

MySQL库、表的基本操作01 一、库操作1.1 查看数据库1.2 创建数据库1.3 选择数据库1.4 查看创建数据库的SQL语句1.5 修改数据库1.6 删除数据库 二、表操作2.1 创建数据表2.2 查看表2.3 查看表结构2.4 查看创建数据库的SQL语句2.5 修改表2.6 删除表 ⚠️MySQL版本 8.0 一、库操作…
阅读更多...
【Golang】go语言异常处理快速学习

【Golang】go语言异常处理快速学习

Go 语言的异常处理与很多传统的编程语言不同&#xff0c;它没有 try/catch 这样的异常捕获机制&#xff0c;而是通过 错误类型&#xff08;error&#xff09;来进行错误处理。Go 语言鼓励显式地处理错误&#xff0c;保持代码的简单性和可维护性。在 Go 中&#xff0c;错误处理不…
阅读更多...
Ollama部署本地大模型DeepSeek-R1-Distill-Llama-70B

Ollama部署本地大模型DeepSeek-R1-Distill-Llama-70B

文章目录 一、下模二、转模1. 下载转换工具2. 安装环境依赖3. llama.cpp1. 转换脚本依赖2. llama.cpp安装依赖包3. llama.cpp编译安装4. 格式转换 三、Ollama部署1. 安装启动Ollama2. 添加模型3. 测试运行 一、下模 #模型下载 from modelscope import snapshot_download model…
阅读更多...
Rust 驱动的 Python 工具革命：Ruff 和 uv 与传统工具的对比分

Rust 驱动的 Python 工具革命：Ruff 和 uv 与传统工具的对比分

Rust 驱动的 Python 工具革命&#xff1a;Ruff 和 uv 与传统工具的对比分析 概述&#xff1a; Python 生态系统长期以来依赖于一系列经典工具&#xff0c;如 Flake8、Black、pip 和 virtualenv&#xff0c;这些工具在代码检查、格式化和依赖管理方面发挥了重要作用。然而&…
阅读更多...
【鸿蒙开发】第三十九章 LazyForEach：数据懒加载

【鸿蒙开发】第三十九章 LazyForEach：数据懒加载

目录 1 背景 2 使用限制 键值生成规则 组件创建规则 首次渲染 非首次渲染 改变数据子属性 使用状态管理V2 拖拽排序 1 背景 LazyForEach从提供的数据源中按需迭代数据&#xff0c;并在每次迭代过程中创建相应的组件。当在滚动容器中使用了LazyForEach&#xff0c;框架…
阅读更多...
通过Python编程语言实现“机器学习”小项目教程案例

通过Python编程语言实现“机器学习”小项目教程案例

以下为你提供一个使用Python实现简单机器学习项目的教程案例&#xff0c;此案例将使用鸢尾花数据集进行分类任务&#xff0c;运用经典的支持向量机&#xff08;SVM&#xff09;算法。 步骤 1&#xff1a;环境准备 首先&#xff0c;你要确保已经安装了必要的Python库&#xff…
阅读更多...
【数据挖掘在量化交易中的应用：特征发现与特征提取】

【数据挖掘在量化交易中的应用：特征发现与特征提取】

好的&#xff0c;我将撰写一篇关于金融领域数据挖掘的技术博客&#xff0c;重点阐述特征发现和特征提取&#xff0c;特别是在量化交易中的应用。我会提供具体的实操步骤&#xff0c;并结合Python和TensorFlow进行代码示例。 完成后&#xff0c;我会通知您进行查看。 数据挖掘…
阅读更多...
最新文章

Copyright @ 2022~2023