-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbinary-search.html
114 lines (112 loc) · 37.1 KB
/
binary-search.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0kTl.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0iNK.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/e5221f7d85b0900837a45fb933fa34ec.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0zdB.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg" as="image" fetchpriority="high"><meta name="keywords" content="二分查找"><link rel="canonical" href="https://jiankychen.github.io/binary-search"><title>二分查找</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">二分查找</h1><div class="meta"><span class="item" title="创建时间：2022-03-12 21:30:06"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-03-12T21:30:06+08:00">2022-03-12</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>3.3k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>3 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0kTl.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0iNK.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/e5221f7d85b0900837a45fb933fa34ec.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0zdB.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Data-Structure/" itemprop="item" rel="index" title="分类于Data Structure"><span itemprop="name">Data Structure<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/binary-search.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><p><strong>二分查找</strong> （binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是用来在一个有序数组中查找某一元素的算法</p>
<p>以在一个升序数组中查找一个数为例：它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么查找右侧；如果中间元素大于所查找的值，查找左侧</p>
<p>时间复杂度：</p>
<ul>
<li>最优时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></li>
<li>最坏和平均时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\log{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">)</span></span></span></span></li>
</ul>
<p>空间复杂度：</p>
<ul>
<li>迭代版本的二分查找算法，空间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></li>
<li>递归版本的二分查找算法，空间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\log{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">)</span></span></span></span></li>
</ul>
<p>基本上所有可以比较的数据类型都可以进行二分查找</p>
<p>一些 <strong>边界情况</strong> ：</p>
<ol>
<li>如何处理答案不存在的情况</li>
<li>区间内没有数字或只有一个 / 两个数字时，代码是否正常工作</li>
<li>数组中有很多个重复元素时，代码是否正常工作</li>
<li>会不会出现死循环</li>
<li>循环结束时， <code>left</code> 与 <code>right</code> 是什么样的关系</li>
</ol>
<p>为避免 <strong>off-by-one</strong> 问题造成的死循环（即， <code>left</code> 始终比 <code>right</code> 小 <code>1</code> ），建议记住以下规律：</p>
<ul>
<li>如果代码用到 <code>left = mid</code> ，把 <code>left</code> 不断向右 push ，那么 <code>mid</code> 向上取整，即 <code>mid = left + right + 1 >> 1</code></li>
<li>如果代码用到 <code>right = mid</code> ，把 <code>right</code> 不断往左 push，那么 <code>mid</code> 向下取整，即 <code>mid = left + right >> 1</code></li>
</ul>
<p>参考：</p>
<ul>
<li>
<p><a target="_blank" rel="noopener" href="https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF">代码随想录：二分查找</a></p>
</li>
<li>
<p><a target="_blank" rel="noopener" href="https://mp.weixin.qq.com/s/1ExIav9uK4bvVnnf4t0H2Q">穿几个马甲，就认不出你是二分法？</a></p>
</li>
</ul>
<h2 id="示例"><a class="anchor" href="#示例">#</a> 示例</h2>
<h3 id="leetcode-题目"><a class="anchor" href="#leetcode-题目">#</a> LeetCode 题目</h3>
<ul>
<li>LeetCode 704. 二分查找</li>
<li>LeetCode 35. 搜索插入位置</li>
<li>LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置</li>
<li>LeetCode 744. 寻找比目标字母大的最小字母</li>
</ul>
<h3 id="求方程的解"><a class="anchor" href="#求方程的解">#</a> 求方程的解</h3>
<p>输出方程 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>x</mi><mn>3</mn></msup><mo>+</mo><mn>16</mn><mo>=</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">x^3 + 16 = 0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8974em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">3</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">16</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">0</span></span></span></span> 的解，已知这个解在 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mo>−</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo separator="true">,</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[-10^9,10^9]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">−</span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">9</span></span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">9</span></span></span></span></span></span></span></span><span class="mclose">]</span></span></span></span> 之间，并且函数 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo><mo>=</mo><msup><mi>x</mi><mn>3</mn></msup><mo>+</mo><mn>16</mn></mrow><annotation encoding="application/x-tex">f(x) = x^3 + 16</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">x</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8974em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">3</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">16</span></span></span></span> 在定义域上单调递增</p>
<p>输出的答案保留 5 位小数</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">double</span> <span class="token function">f</span><span class="token punctuation">(</span> <span class="token keyword">double</span> x <span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">return</span> x <span class="token operator">*</span> x <span class="token operator">*</span> x <span class="token operator">+</span> <span class="token number">16</span><span class="token punctuation">;</span> <span class="token comment">// 函数 f (x)</span></pre></td></tr><tr><td data-num="3"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="4"></td><td><pre></pre></td></tr><tr><td data-num="5"></td><td><pre><span class="token keyword">double</span> <span class="token function">solve</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">double</span> L <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1e9</span><span class="token punctuation">,</span> R <span class="token operator">=</span> <span class="token number">1e9</span><span class="token punctuation">;</span> <span class="token comment">// 方程解在 [L,R] 之间，且函数在 [L,R] 上单调增</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">while</span><span class="token punctuation">(</span> R <span class="token operator">-</span> L <span class="token operator">>=</span> <span class="token number">1e-6</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 精确到 6 位小数，然后四舍五入</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">double</span> M <span class="token operator">=</span> L <span class="token operator">+</span> <span class="token punctuation">(</span>R <span class="token operator">-</span> L<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2.0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">f</span><span class="token punctuation">(</span>M<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> M<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">f</span><span class="token punctuation">(</span>M<span class="token punctuation">)</span> <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span> L <span class="token operator">=</span> M <span class="token operator">+</span> <span class="token number">1e-6</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">f</span><span class="token punctuation">(</span>M<span class="token punctuation">)</span> <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">)</span> R <span class="token operator">=</span> M <span class="token operator">-</span> <span class="token number">1e-6</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">return</span> L<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="15"></td><td><pre></pre></td></tr><tr><td data-num="16"></td><td><pre><span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token function">printf</span><span class="token punctuation">(</span> <span class="token string">"%.5lf\n"</span><span class="token punctuation">,</span> <span class="token function">solve</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>若要求精确到 10 位小数：由于 <code>double</code> 本身存在不小的精度误差，如果通过 <code>R - L >= 1e-10</code> 这种方式来控制二分的终止条件，会带来非常大的精度问题</p>
<p>这种时候，可以采用 <code>固定次数二分</code> 的方法</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">double</span> L <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1e9</span><span class="token punctuation">,</span> R <span class="token operator">=</span> <span class="token number">1e9</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">for</span><span class="token punctuation">(</span> <span class="token keyword">int</span> times <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> times <span class="token operator"><</span> <span class="token number">100</span><span class="token punctuation">;</span> <span class="token operator">++</span>times <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 二分 100 次</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">double</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>L <span class="token operator">+</span> R<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2.0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token comment">// 此处省略二分内容</span></pre></td></tr><tr><td data-num="5"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><blockquote>
<p>在 <code>double</code> 上二分时，尽量使用 <code>固定次数二分</code> 的方法</p>
</blockquote>
<h2 id="lower_bound-和-upper_bound"><a class="anchor" href="#lower_bound-和-upper_bound">#</a> lower_bound 和 upper_bound</h2>
<p>C++ 标准库中有两个使用二分查找的函数： <code>lower_bound</code> 和 <code>upper_bound</code> ，二者均定义于头文件 <code><algorithm></code> 中</p>
<ul>
<li>
<p><code>lower_bound</code> ：在指定的升序排序的数组中，找到第一个大于等于 <code>x</code> 的数字</p>
</li>
<li>
<p><code>upper_bound</code> ：在指定的升序排序的数组中，找到第一个大于 <code>x</code> 的数字</p>
</li>
</ul>
<p>这两个函数会返回对应数字的指针（或者是迭代器）</p>
<pre><code>#include <algorithm>
int *p = lower_bound(first, last, value); // Returns an iterator pointing to the first element in the range [first, last) that is not less than value, or last if no such element is found.
int *q = lower_bound(first, last, value, comp); // given comparison function comp
</code></pre>
<p>巧妙地运用这两个函数，可以完成所有常见的二分查找操作：</p>
<ul>
<li>找到第一个大于等于 x 的数字</li>
<li>找到第一个大于 x 的数字</li>
<li>找到最后一个等于 x 的数字</li>
<li>查找数组中是否有数字 x</li>
<li>查询数组中有几个数字 x</li>
<li>找到最后一个小于 x 的数字</li>
<li>……</li>
</ul>
<p>参考：<a target="_blank" rel="noopener" href="https://en.cppreference.com/w/cpp/algorithm/lower_bound">cppreference</a></p>
<div class="tags"><a href="/tags/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/" rel="tag"><i class="ic i-tag"></i>二分查找</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 16:40:44" itemprop="dateModified" datetime="2024-06-08T16:40:44+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/binary-search.html" title="二分查找">https://jiankychen.github.io/binary-search.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/cpp-vectors.html" rel="prev" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/470d00578173666b5183f4631e51a421.jpg" title="C++ 字符串、向量和数组"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>C++</span><h3>C++ 字符串、向量和数组</h3></a></div><div class="item right"><a href="/leetcode-binarysearch.html" rel="next" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/YQSYM.jpg" title="LeetCode - 二分查找专题"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 二分查找专题</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%A4%BA%E4%BE%8B"><span class="toc-number">1.</span> <span class="toc-text"> 示例</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#leetcode-%E9%A2%98%E7%9B%AE"><span class="toc-number">1.1.</span> <span class="toc-text"> LeetCode 题目</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B1%82%E6%96%B9%E7%A8%8B%E7%9A%84%E8%A7%A3"><span class="toc-number">1.2.</span> <span class="toc-text"> 求方程的解</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#lower_bound-%E5%92%8C-upper_bound"><span class="toc-number">2.</span> <span class="toc-text"> lower_bound 和 upper_bound</span></a></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li class="active"><a href="/binary-search.html" rel="bookmark" title="二分查找">二分查找</a></li><li><a href="/binary-tree.html" rel="bookmark" title="二叉树">二叉树</a></li><li><a href="/algorithm-complexity.html" rel="bookmark" title="算法复杂度">算法复杂度</a></li><li><a href="/date-structure.html" rel="bookmark" title="数据结构简介">数据结构简介</a></li><li><a href="/sort-algorithm.html" rel="bookmark" title="排序">排序</a></li><li><a href="/recursive.html" rel="bookmark" title="递推与递归">递推与递归</a></li><li><a href="/dynamic-programming.html" rel="bookmark" title="动态规划">动态规划</a></li><li><a href="/priority-queue.html" rel="bookmark" title="优先级队列">优先级队列</a></li><li><a href="/hash-table.html" rel="bookmark" title="哈希表">哈希表</a></li><li><a href="/graphics-theory.html" rel="bookmark" title="图">图</a></li><li><a href="/KMP.html" rel="bookmark" title="KMP 算法">KMP 算法</a></li><li><a href="/traverse.html" rel="bookmark" title="回溯">回溯</a></li><li><a href="/Dijkstra.html" rel="bookmark" title="Dijkstra">Dijkstra</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/leetcode-binarysearch.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/cpp-vectors.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/cpp-classes.html">C++ 类</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-greedy.html">LeetCode - 贪心专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/dynamic-programming.html">动态规划</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-monotonicstacks.html">LeetCode - 单调栈专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/KMP.html">KMP 算法</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/binary-tree.html">二叉树</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/traverse.html">回溯</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-oop.html">Python 面向对象</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/sort-algorithm.html">排序</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/recursive.html">递推与递归</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/binary-search`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>