二分算法刷题

1. 初识

总结:二分算法题的细节非常多,容易写出死循环。使用算法的条件不一定是数组有序,而是具有“二断性”;模板三种后面会讲。

  • 朴素二分
  • 二分查找左端点
  • 二分查找右端点

2. 朴素二分

题目链接:704. 二分查找 - 力扣(LeetCode)

循序渐进,先从暴力解法说起。

  1. 暴力解法:遍历全部数组,判断是否==target。时间复杂度O(n)。但是这里没有把数组是有序的这个条件给用上。
  2. 二分查找算法:

“二段性”,当我们发现:我们发现一个规律,在选择一个状态的时候,能够直接丢弃掉“一半”的情况。

只要选取的位置能够将全部情况划分为两个情况就可以,可以是二分之一点,要和可以是三分之一点。

但是从概率上来讲,还是每次选取二分之一点的效率最好。

编写代码

class Solution {public int search(int[] nums, int target) {int left = 0; int right = nums.length -1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else if (nums[mid] > target) right = mid - 1;else return mid;}return -1;}
}

朴素二分模板

朴素二分求mid的时候使用( left + right)/ 2 还是使用(left + right + 1)/2都是一样的

3. 在排序数组中查找元素的第一个位置和最后一个位置。(查找区间左端点、右端点)

题目链接:34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

3.1. 暴力解法

遍历查找,第一次遇到这target标记下标,然后继续往后遍历,直到第一次找到大于target的下标。

3.2. 二分

暴力算法同样没有使用数组是有序的这个重要条件。

先来看看朴素二分能不能解决问题?

是不能的,朴素二分只能保证找到target,但是并不能保证找到的index就是边界啊。

因此就引出了另外两种二分:查找左端点、查找右端点的二分。

3.2.1. 查找左端点

朴素二分是将数组划分成3个状态(大于的、小于的、等于的)。

而查找左端点的时候是不可以将数组划分为三个状态的,这是因为的等于状态的位置请不确定,需要将其和大于状态划分到一起,这个等于的点,有可能刚好就是我们要找的左端点。

这样划分之后,

如果mid落在了【小于target】的这一段区间中,我们的mid该怎么更新状态呢?由于这里已经小于了target,而我们的目标是找到target的左端点,所以mid = mid+1.

如果mid落在了【大于等于target】这一段的区间中,mid则 mid = right,这是因为right很有可能就是我们想要寻找的左端点,不可以跳过。

那么循环的条件是什么?

无论是【】区间中有结果,还是区间中所有的数字都大于target,或者是小于target,最终,当最终left和right重合的时候,都不需要到循环中再次判断了,这就是最终状态,只需要判断这个时候的left是不是等于target即可。

如果当left==right时候,在进入循环就会陷入死循环。

求mid的操作是什么?

这里是求左端点,所以mid = (right - left )/ 2;或者 mid = left + (right-left) /2;

如果使用 mid = left +(right - left + 1) / 2;也会死循环

3.2.2. 查找右端点

原理同上。注意二段性的运用

3.2.3. 代码

class Solution {public int[] searchRange(int[] nums, int target) {if(nums.length == 0) return new int[]{-1 ,-1};int[] ret = new int[2];int left = findLeft(nums,target);int right = findRight(nums,target);ret[0] = left; ret[1] = right;return ret;}private static int findLeft(int[] nums , int target){int left = 0 , right = nums.length - 1;int mid = 0;while(left < right){mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}if(nums[left] != target) return  -1;else return left;}private static int findRight(int[] nums , int target){int left = 0 , right = nums.length - 1;int mid = 0;while(left < right){mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid ;else right = mid -1;}if(nums[left] != target) return  -1;else return right;}
} 

3.2.4. 模板

不要死记硬背!理解

记住:就中间坐标的方式,其他的可以关联记忆!(分析二段性 --> 分析求中点mid应该怎么求(当下面出现剑法,求mid就有+1;反之则反)),具体的分类讨论的代码,就题论题。分析好中点落在某个区间的时候,left、以及right如何变化。

4. x的平方根

题目链接:69. x 的平方根 - 力扣(LeetCode)

4.1. 暴力解法

从1开始,一次遍历,计算i*i 和 x的大小。

这个大小具体满足什么要求?来看题目,题目要求返回的是整数,小数部分就会被舍去。也就是找到最大的i,满足i*i <= x.

4.2. 二分

暴力解法中其实已经看到了 二段性,在计算i*i的时候,如果不能满足要求,就可以直接排除掉“另一半”的数据量。从上面的分析也可以很清楚的看到,我们需要寻找的就是“满足条件”的数据的右端点。也就是找到 找到最大的i,满足i*i <= x.

进入循环的条件:while(left < right)

求mid的方式 : mid = left + (right -left + 1)/ 2;

开始二分

if (i*i <= x)left = mid;(因为求的是 右端点,这里有可能是等于的情况,也就是右端点,因此不可以left = mid + 1).

if (i*I > x) right = mid -1; (这里已经大于了,不可能包含我们需要的数据)

代码

class Solution {public int mySqrt(int x) {if (x == 0 || x == 1) return x;long left = 1, right = x;long mid;while(left < right){mid = left + (right - left + 1) / 2;if(mid * mid <= x) left = mid;else right = mid -1;}return (int)left;}
}

5. 搜索插入顺序

题目链接:

35. 搜索插入位置 - 力扣(LeetCode)

5.1. 暴力解法

遍历数组,找到第一个等会或者大于target的数字,返回其下标。

5.2. 二分

实际上就是适用二分法求取区间的左端点,该区间是大于等于target的这个区间。

进入循环的条件 while(left< right)

求mid = left+(right - left) / 2;

if(nums[i] < target)left = mid+1; 该区间没有满足的情况,直接跳出;

if(nums[i] >= target) right = mid; 该区间有可能,存在【左端点】,也就是恰好nums[i] == target.

结束循环后。left=right,需要判断这时候是存在nums[left] == target,还是不存在,需要返回插入的下标(此时,nunms[left] < target,返回left+1)

代码:

class Solution {public int searchInsert(int[] nums, int target) {int left = 0 , right = nums.length - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}if(nums[left] < target) return left + 1;return left;}
}

6. 山脉数组的峰值

题目链接:852. 山脉数组的峰顶索引 - 力扣(LeetCode)

6.1. 暴力解法

遍历数组中的元素,逐一判断该值是否是【峰值】,峰值的话就是大于前驱,同时也大于后继。

6.2. 二分

这道题目的难点在于,如何能看出来使用二分。

前面说过,二分的题目是看数据的二段性,这道题目的二段性在哪里?

class Solution {public int peakIndexInMountainArray(int[] arr) {int left =  0, right = arr.length - 1;while(left < right){int mid = left + (right - left ) / 2;if(arr[mid] < arr[mid + 1]) left = mid + 1;else right = mid;}return left;}
}

7. 搜索旋转排序数组中的最小值

题目链接:153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

7.1. 暴力解法

遍历数组,通过比较记录数组中的最小元素,得到的就是最小值。

此时,并没有使用到数组的特殊性质,该数组使用过升序数组“旋转”得到的。

7.2. 二分

为什么能使用二分?

代码:

public int findMin(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;// 如果中间元素大于右边界元素,说明最小值在右半部分if (nums[mid] > nums[right]) {left = mid + 1;} else {// 否则,最小值在左半部分或是mid本身right = mid;}}return nums[left];}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34616.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

itsdangerous加解密源码分析|BUG汇总

这是我这两天的思考 早知道密码学的课就不旷那么多了 纯个人见解 如需转载&#xff0c;标记出处 目录 一、官网介绍 二、事例代码 源码分析&#xff1a; 加密函数dump源码使用的函数如下&#xff1a; 解密 ​编辑 ​编辑 关于签名&#xff1a; 为什么这个数字签名没有…

深度解析React Native底层核心架构

React Native 工作原理深度解析 一、核心架构&#xff1a;三层异构协作体系 React Native 的跨平台能力源于其独特的 JS层-Shadow层-Native层 架构设计&#xff0c;三者在不同线程中协同工作&#xff1a; JS层 运行于JavaScriptCore&#xff08;iOS&#xff09;或Hermes&…

前端内存优化实战指南:从内存泄漏到性能巅峰

前端内存优化实战指南&#xff1a;从内存泄漏到性能巅峰 一、内存问题引发的场景 1.1 典型内存灾难现场 // 经典内存泄漏示例 const zombieElements new Set();function createLeak() {const div document.createElement(div);zombieElements.add(div); // 元素永不释放div…

【工作记录】pytest使用总结

1、 fixture夹具 可参考&#xff1a; python3.x中 pytest之fixture - 漂泊的小虎 - 博客园 fixture是指夹具&#xff08;把用例夹在中间&#xff09;&#xff0c;它包括前置工作和后置工作&#xff0c;前置是用例代码的准备阶段&#xff0c;后置是用例执行之后的清理阶段,用…

C++基础笔记

1. C关键字 这个不多说&#xff0c;以后接触得到&#xff0c;但这里做个总结&#xff1a; 2. 命名空间 一般类型&#xff1a; namespace Xianyu {// 命名空间中可以定义变量/函数/类型int rand 10;int Add(int left, int right){return left right;}struct Node{struct No…

生活中的可靠性小案例12:类肤材质老化发粘问题

我一直觉得我买的某品牌车载吸尘器很好用&#xff0c;用了几年&#xff0c;目前性能也是杠杠的。然而它现在有个最大的问题&#xff0c;就是表面发粘了&#xff0c;用起来粘手&#xff0c;非常不舒服。 这一类问题在生活中不少见&#xff0c;尤其是一些用了类肤材质涂层的物件。…

黑马node.js教程(nodejs教程)——AJAX-Day01-04.案例_地区查询——查询某个省某个城市所有地区(代码示例)

文章目录 代码示例效果 代码示例 axiosTest.html <!DOCTYPE html> <!-- 文档类型声明&#xff0c;告诉浏览器这是一个HTML5文档 --> <html lang"en"> <!-- HTML根元素&#xff0c;设置文档语言为英语 --><head> <!-- 头部区域&am…

Ollama+OpenWebUI本地部署大模型

OllamaOpenWebUI本地部署大模型 前言Ollama使用Ollama安装Ollama修改配置Ollama 拉取远程大模型Ollama 构建本地大模型Ollama 运行本地模型&#xff1a;命令行交互Api调用Web 端调用 总结 前言 Ollama是一个开源项目&#xff0c;用于在本地计算机上运行大型语言模型&#xff0…

【NeurIPS 2024】LLM-ESR:用大语言模型破解序列推荐的长尾难题

标题期刊年份关键词LLM-ESR: Large Language Models Enhancement for Long-tailed Sequential RecommendationNeurIPS2024Large Language Models, Sequential Recommendation, Long-tailed &#x1f4da;研究背景 在电商和社交媒体的世界里&#xff0c;序列推荐系统&#xff…

C语言_数据结构总结9:树的基础知识介绍

1. 树的基本术语 - 祖先&#xff1a;考虑结点K&#xff0c;从根A到结点K的唯一路径上的所有其它结点&#xff0c;称为结点K的祖先。 - 子孙&#xff1a;结点B是结点K的祖先&#xff0c;结点K是B的子孙。结点B的子孙包括&#xff1a;E,F,K,L。 - 双亲&#xff1a;路径上…

Android 14 Telephony 网络选择功能介绍

一、总体介绍 (一)功能 手动搜网的流程:用户通过UI触发,调用TelephonyManager的API,比如startNetworkScan,然后这个请求会传递到RIL层,通过AT命令与基带通信,进行网络扫描。结果返回后,经过TelephonyRegistry通知应用层。中间可能涉及IPC,比如Binder通信,因为应用和…

系统思考全球化落地

感谢加密货币公司Bybit的再次邀请&#xff0c;为全球团队分享系统思考课程&#xff01;虽然大家来自不同国家&#xff0c;线上学习的形式依然让大家充满热情与互动&#xff0c;思维的碰撞不断激发新的灵感。 尽管时间存在挑战&#xff0c;但我看到大家的讨论异常积极&#xff…

位运算(基础算法)

按位与AND&#xff08; & &#xff09; 只有当两个位都为1时&#xff0c;结果才为1,否则为0。结果不会变大 按位或 OR&#xff08; | &#xff09; 只有当两个位中有一个为1时&#xff0c;结果才为1,否则为0。结果不会变小 按位异或 XOR &#xff08; ^ &#xff09; 只…

规模效应的三重边界:大白话解读-deepseek为例

前言&#xff1a;当Scaling Laws遇见边际递减效应 在人工智能的狂飙突进中&#xff0c;大语言模型如同不断膨胀的星体&#xff0c;吞噬着海量算力与数据。OpenAI于2020年揭开的Scaling Laws&#xff0c;曾为这场盛宴指明方向&#xff1a;模型性能随参数规模&#xff08;N&…

力扣143重排链表

143. 重排链表 给定一个单链表 L 的头节点 head &#xff0c;单链表 L 表示为&#xff1a; L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为&#xff1a; L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的…

wow-rag:task3-初步体验问答引擎

做RAG需要自己准备一个txt文档&#xff0c;新建一个docs文件夹&#xff0c;放进去。例如&#xff0c;这里放了一个./docs/问答手册.txt # 从指定文件读取&#xff0c;输入为List from llama_index.core import SimpleDirectoryReader,Document documents SimpleDirectoryRead…

bgp服务器是什么意思

一、基础概念 ‌BGP服务器‌&#xff08;Border Gateway Protocol Server&#xff09;指通过 ‌边界网关协议&#xff08;BGP&#xff09;‌ 实现 ‌多运营商线路智能调度‌ 的服务器&#xff0c;能够自动选择最优路径连接不同网络&#xff08;如电信、联通、移动&#xff09;…

AtCoder Beginner Contest 397(ABCDE)

目录 A - Thermometer 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; B - Ticket Gate Log 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; C - Variety Split Easy 翻译&#xff1a; 思路&#xff1a; 实现&#xff1a; D - Cubes 翻译&#xff1a…

unserialize3 [有难度,序列化反序列化知识点]

详情: 地址:https://adworld.xctf.org.cn/challenges/list (unserialize3) 看到题目名称是反序列化 代码审计 <?php class xctf{// 定义一个公有属性$flag&#xff0c;通常CTF题目中需要获取该属性值public $flag 111; // 此处为示例值&#xff0c;实际可能为真实flag/*…

【Linux-传输层协议TCP】TCP协议段格式+确认应答+超时重传+连接管理机制(三次握手、四次挥手、理解TIME_WAIT + CLOSE_WAIT)

TCP协议 TCP全称为“传输控制协议&#xff08;Transmission Control Protocol&#xff09;”人如其名&#xff0c;要对数据的传输进行一个详细的控制。 1.TCP协议段格式 下面是TCP报头各个字段的表格形式&#xff1a; 字段名称字段大小描述源端口16位发送端TCP端口号。目的端…