~dkuhlman/python-training-materials/Materials

<h1>8.6. <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-mod docutils literal">bisect</code></a> — Array bisection algorithm<a class="headerlink" href="#module-bisect" title="Permalink to this headline">¶</a></h1>

Source code: <a class="reference external" href="https://hg.python.org/cpython/file/3.5/Lib/bisect.py">Lib/bisect.py</a>

This module provides support for maintaining a list in sorted order without

having to sort the list after each insertion. For long lists of items with

expensive comparison operations, this can be an improvement over the more common

approach. The module is called <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-mod docutils literal">bisect</code></a> because it uses a basic bisection

algorithm to do its work. The source code may be most useful as a working

example of the algorithm (the boundary conditions are already right!).

The following functions are provided:

<code class="descclassname">bisect.</code><code class="descname">bisect_left</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.bisect_left" title="Permalink to this definition">¶</a></dt>

<dd>Locate the insertion point for x in a to maintain sorted order.

The parameters lo and hi may be used to specify a subset of the list

which should be considered; by default the entire list is used. If x is

already present in a, the insertion point will be before (to the left of)

any existing entries. The return value is suitable for use as the first

parameter to <code class="docutils literal">list.insert()</code> assuming that a is already sorted.

The returned insertion point i partitions the array a into two halves so

that <code class="docutils literal">all(val < x for val in a[lo:i])</code> for the left side and

<code class="docutils literal">all(val >= x for val in a[i:hi])</code> for the right side.

100

</dd></dl>

101

102

103

104

<code class="descclassname">bisect.</code><code class="descname">bisect_right</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.bisect_right" title="Permalink to this definition">¶</a></dt>

105

106

<code class="descclassname">bisect.</code><code class="descname">bisect</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.bisect" title="Permalink to this definition">¶</a></dt>

107

<dd>Similar to <a class="reference internal" href="#bisect.bisect_left" title="bisect.bisect_left"><code class="xref py py-func docutils literal">bisect_left()</code></a>, but returns an insertion point which comes

108

after (to the right of) any existing entries of x in a.

109

The returned insertion point i partitions the array a into two halves so

110

that <code class="docutils literal">all(val <= x for val in a[lo:i])</code> for the left side and

111

<code class="docutils literal">all(val > x for val in a[i:hi])</code> for the right side.

112

</dd></dl>

113

114

115

116

<code class="descclassname">bisect.</code><code class="descname">insort_left</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.insort_left" title="Permalink to this definition">¶</a></dt>

117

<dd>Insert x in a in sorted order. This is equivalent to

118

<code class="docutils literal">a.insert(bisect.bisect_left(a, x, lo, hi), x)</code> assuming that a is

119

already sorted. Keep in mind that the O(log n) search is dominated by

120

the slow O(n) insertion step.

121

</dd></dl>

122

123

124

125

<code class="descclassname">bisect.</code><code class="descname">insort_right</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.insort_right" title="Permalink to this definition">¶</a></dt>

126

127

<code class="descclassname">bisect.</code><code class="descname">insort</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.insort" title="Permalink to this definition">¶</a></dt>

128

<dd>Similar to <a class="reference internal" href="#bisect.insort_left" title="bisect.insort_left"><code class="xref py py-func docutils literal">insort_left()</code></a>, but inserting x in a after any existing

129

entries of x.

130

</dd></dl>

131

132

133

See also

134

<a class="reference external" href="http://code.activestate.com/recipes/577197-sortedcollection/">SortedCollection recipe</a> that uses

135

bisect to build a full-featured collection class with straight-forward search

136

methods and support for a key-function. The keys are precomputed to save

137

unnecessary calls to the key function during searches.

138

</div>

139

140

<h2>8.6.1. Searching Sorted Lists<a class="headerlink" href="#searching-sorted-lists" title="Permalink to this headline">¶</a></h2>

141

The above <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal">bisect()</code></a> functions are useful for finding insertion points but

142

can be tricky or awkward to use for common searching tasks. The following five

143

functions show how to transform them into the standard lookups for sorted

144

lists:

145

<div class="highlight-python3"><div class="highlight"><pre>def index(a, x):

146

'Locate the leftmost value exactly equal to x'

147

i = bisect_left(a, x)

148

if i != len(a) and a[i] == x:

149

return i

150

raise ValueError

151

152

def find_lt(a, x):

153

'Find rightmost value less than x'

154

155

if i:

156

return a[i-1]

157

raise ValueError

158

159

def find_le(a, x):

160

'Find rightmost value less than or equal to x'

161

i = bisect_right(a, x)

162

if i:

163

return a[i-1]

164

raise ValueError

165

166

def find_gt(a, x):

167

'Find leftmost value greater than x'

168

169

if i != len(a):

170

return a[i]

171

raise ValueError

172

173

def find_ge(a, x):

174

'Find leftmost item greater than or equal to x'

175

176

if i != len(a):

177

return a[i]

178

raise ValueError

179

</pre></div>

180

</div>

181

</div>

182

183

<h2>8.6.2. Other Examples<a class="headerlink" href="#other-examples" title="Permalink to this headline">¶</a></h2>

184

The <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal">bisect()</code></a> function can be useful for numeric table lookups. This

185

example uses <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal">bisect()</code></a> to look up a letter grade for an exam score (say)

186

based on a set of ordered numeric breakpoints: 90 and up is an ‘A’, 80 to 89 is

187

a ‘B’, and so on:

188

<div class="highlight-python3"><div class="highlight"><pre>>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):

189

... i = bisect(breakpoints, score)

190

... return grades[i]

191

...

192

>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]

193

['F', 'A', 'C', 'C', 'B', 'A', 'A']

194

</pre></div>

195

</div>

196

Unlike the <a class="reference internal" href="functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal">sorted()</code></a> function, it does not make sense for the <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal">bisect()</code></a>

197

functions to have key or reversed arguments because that would lead to an

198

inefficient design (successive calls to bisect functions would not “remember”

199

all of the previous key lookups).

200

Instead, it is better to search a list of precomputed keys to find the index

201

of the record in question:

202

<div class="highlight-python3"><div class="highlight"><pre>>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]

203

>>> data.sort(key=lambda r: r[1])

204

>>> keys = [r[1] for r in data] # precomputed list of keys

205

>>> data[bisect_left(keys, 0)]

206

('black', 0)

207

208

('blue', 1)

209

210

('red', 5)

211

212

('yellow', 8)

213

</pre></div>

214

</div>

215

</div>

216

</div>

217

218

219

</div>

220

</div>

221

</div>

222

223

224

<h3><a href="../contents.html">Table Of Contents</a></h3>

225

<ul>

226

<li><a class="reference internal" href="#">8.6. <code class="docutils literal">bisect</code> — Array bisection algorithm</a><ul>

227

<li><a class="reference internal" href="#searching-sorted-lists">8.6.1. Searching Sorted Lists</a></li>

228

<li><a class="reference internal" href="#other-examples">8.6.2. Other Examples</a></li>

229

</ul>

230

</li>

231

</ul>

232

233

<h4>Previous topic</h4>

234

<a href="heapq.html"

235

title="previous chapter">8.5. <code class="docutils literal">heapq</code> — Heap queue algorithm</a>

236

<h4>Next topic</h4>

237

<a href="array.html"

238

title="next chapter">8.7. <code class="docutils literal">array</code> — Efficient arrays of numeric values</a>

239

240

241

<li><a href="../bugs.html">Report a Bug</a></li>

242

<li><a href="../_sources/library/bisect.txt"

243

rel="nofollow">Show Source</a></li>

244

</ul>

245

246

247

<h3>Quick search</h3>

248

249

250

251

252

253

</form>

254

255

Enter search terms or a module, class or function name.

256

257

</div>

258

259

</div>

260

</div>

261

262

</div>

263

264

<h3>Navigation</h3>

265

<ul>

266

267

<a href="../genindex.html" title="General Index"

268

>index</a></li>

269

270

<a href="../py-modindex.html" title="Python Module Index"

271

>modules</a> |</li>

272

273

<a href="array.html" title="8.7. array — Efficient arrays of numeric values"

274

>next</a> |</li>

275

276

<a href="heapq.html" title="8.5. heapq — Heap queue algorithm"

277

>previous</a> |</li>

278

<li><img src="../_static/py.png" alt=""

279

style="vertical-align: middle; margin-top: -1px"/></li>

280

<li><a href="https://www.python.org/">Python</a> »</li>

281

<li>

282

3.5.1

283

<a href="../index.html">Documentation </a> »

284

</li>

285

286

<li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> »</li>

287

<li class="nav-item nav-item-2"><a href="datatypes.html" >8. Data Types</a> »</li>

288

</ul>

289

</div>

290

291

292

293

The Python Software Foundation is a non-profit corporation.

294

<a href="https://www.python.org/psf/donations/">Please donate.</a>

295

296

Last updated on Jan 22, 2016.

297

<a href="../bugs.html">Found a bug</a>?

298

299

Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.3.3.

300

</div>

301

302

</body>

303

</html>

b'\\ No newline at end of file'

Older »