【代码随想录】LC 704. 二分查找

简介: 防止溢出可以将int mid = (left + right) / 2;改为 int mid = left + ((right - left) / 2);或int mid = left + ((right - left) >> 1);。数组理论基础数组下标都是从0开始的数组在内存空间的地址是连续的数组中的元素只能覆盖,不能删除。

一、题目

1、原题链接

704. 二分查找


2、题目描述

b161e16bb32888c7bc18adbc0802a024_b74e9426f2ce4ed18a238f20cfdbe429.png


二、解题报告

1、思路分析

二分查找有一般有两种写法,主要思想是利用搜索区间的定义来确定代码条件:


[left,right](左闭右闭)

如果将区间定义为左闭右闭,则意味着left和right的值都可以取到,而且left和right的值可以相等。所以:

初始left=0、right=nums.size()-1。

循环条件需要设置为left<=right

当nums[mid]>target时,更新right=mid-1。(因为根据区间定义,此时如果使right=mid,区间可以取到mid,而已知mid不满足条件,故应将区间缩小为[left,mid-1])

当nums[mid]<target时,更新为left=mid+1。(因为根据区间定义,此时如果使left=mid,区间可以取到mid,而已知mid不满足条件,故应将区间缩小为[mid+1,right])

当nums[mid]==target时,返回mid。

否则,返回-1。

[left,right)(左闭右开)

如果将区间定义为左闭右开,则意味着left的值可以取到,而right的值取不到,而且left和right的值不可以相等。所以:

初始left=0、right=nums.size()。

循环条件需要设置为left<right

当nums[mid]>target时,更新right=mid。(因为根据区间定义,此时如果使right=mid-1,区间取不到mid-1,会使搜索区间丢失mid-1,故应将区间缩小为[left,mid))

当nums[mid]<target时,更新left=mid+1。(因为根据区间定义,此时如果使left=mid,区间可以取到mid,而已知mid不满足条件,故应将区间缩小为[mid+1,right))

当nums[mid]==target时,返回mid。

否则,返回-1。

2、时间复杂度

二分查找时间复杂度为O (log n)


3、代码详解

左闭右闭区间定义代码


class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            //防止溢出可以改为:
            //int mid = left + ((right - left) / 2);
            //或
            //int mid = left + ((right - left) >> 1);
            int mid = (left + right) / 2;
            if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};


左闭右开区间定义代码


class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            //防止溢出可以改为:
            //int mid = left + ((right - left) / 2);
            //或
            //int mid = left + ((right - left) >> 1);
            int mid = (left + right) / 2;
            if (nums[mid] > target) right = mid;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};


三、知识风暴

注意mid是下标不是值,与target比较时是用nums[mid]。

防止溢出可以将int mid = (left + right) / 2;改为 int mid = left + ((right - left) / 2);或int mid = left + ((right - left) >> 1);。

数组理论基础

数组下标都是从0开始的

数组在内存空间的地址是连续的

数组中的元素只能覆盖,不能删除。

-dzk-
+关注
目录
打赏
0
0
0
0
8
分享
相关文章
关于Sectigo证书那些事儿
Sectigo(原Comodo CA)成立于1998年,是全球领先的证书颁发机构之一,SSL证书市场占有率近40%。其提供SSL证书、代码签名证书、邮件安全证书及文档签名证书等丰富数字证书产品,支持多平台兼容。Sectigo以高安全性、全球信任、高性价比著称,广泛应用于网站加密、软件签名、邮件保护和文档验证等领域,助力企业保障在线业务安全与可信。近期动态包括收购Entrust可信CA业务、与IONOS战略合作及获网络安全奖项等。
短视频创作助手 | AI剧本生成与动画创作
短视频行业的快速发展得益于移动互联网和智能手机的普及,4G、5G网络的推广使用户对视频内容的需求大增。短视频以其短小精悍、易于传播的特点迅速吸引了大量用户。平台如抖音、快手通过算法推荐和社交功能推动了用户增长和内容生态繁荣。AI剧本生成与动画创作方案则进一步降低了创作门槛,简化从剧本到视频成片的过程。该方案利用阿里云的大模型服务平台百炼、函数计算FC和对象存储OSS等产品,实现了自动化流程,涵盖故事剧本撰写、插图设计、声音合成至视频合成,极大缩短了创作周期,提高了内容产出速度。部署简单快捷,耗时约5分钟,使得非技术人员也能轻松上手,满足企业和个人创作者的需求。
阿里云百炼应用实践系列-基于LlamaIndex的文档问答助手
本文以阿里云百炼官方文档问答助手为例,介绍如何基于阿里云百炼平台打造基于LlamaIndex的RAG文档问答产品。我们基于阿里云百炼平台的底座能力,以官方帮助文档为指定知识库,搭建了问答服务,支持钉钉、Web访问。介绍了相关技术方案和主要代码,供开发者参考。
1305 22
浅析Python中的异步编程:从asyncio到Tornado
Python的异步编程是提升应用性能的关键。本文从Python的异步编程概念入手,探讨了asyncio库的使用及其在实际开发中的应用,并分析了Tornado框架的异步模型,以及如何将异步思维运用于实际项目中。
Maxwell:binlog 解析器,轻松同步 MySQL 数据
Maxwell:binlog 解析器,轻松同步 MySQL 数据
988 11
Windows 中的硬链接、目录联接(软链接)、符号链接、快捷方式
【10月更文挑战第5天】本文介绍了四种链接类型的概念及用途:硬链接允许通过多个入口访问同一文件内容,适用于不复制文件的情况下提供多处访问;软链接(目录联接)用于创建目录间的虚拟映射,可跨越文件系统;符号链接则更为灵活,可链接文件或目录并指向任意路径;快捷方式则是Windows中常用的一种特殊文件类型,便于快速访问程序、文件或网络资源。分别描述了它们的定义、工作原理、特点以及创建方法。
1860 10
Linux设备驱动开发详解1
Linux设备驱动开发详解
154 5
TCP面向连接
【8月更文挑战第19天】
251 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问