infx511.github.io/searching.html at master · infx511/infx511.github.io · GitHub

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
<!DOCTYPE html>
<html lang="en" xml:lang="en">
<head>

  <meta charset="utf-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <title>Chapter 7 Searching and Filtering | Introduction to Programming</title>
  <meta name="description" content="Course reader for IMT/LIS 511: Introduction to Programming for Information and Data Science." />
  <meta name="generator" content="bookdown 0.24 and GitBook 2.6.7" />

  <meta property="og:title" content="Chapter 7 Searching and Filtering | Introduction to Programming" />
  <meta property="og:type" content="book" />
  <meta property="og:url" content="https://infx511.github.io/" />

  <meta property="og:description" content="Course reader for IMT/LIS 511: Introduction to Programming for Information and Data Science." />
  <meta name="github-repo" content="infx511/book" />

  <meta name="twitter:card" content="summary" />
  <meta name="twitter:title" content="Chapter 7 Searching and Filtering | Introduction to Programming" />

  <meta name="twitter:description" content="Course reader for IMT/LIS 511: Introduction to Programming for Information and Data Science." />


<meta name="author" content="Joel Ross" />


<meta name="date" content="2023-07-26" />

  <meta name="viewport" content="width=device-width, initial-scale=1" />
  <meta name="apple-mobile-web-app-capable" content="yes" />
  <meta name="apple-mobile-web-app-status-bar-style" content="black" />

  <link rel="shortcut icon" href="img/ischool-gold.png" type="image/x-icon" />
<link rel="prev" href="dictionaries.html"/>
<link rel="next" href="functional-programming.html"/>
<script src="libs/header-attrs-2.11/header-attrs.js"></script>
<script src="libs/jquery-3.6.0/jquery-3.6.0.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/fuse.js@6.4.6/dist/fuse.min.js"></script>
<link href="libs/gitbook-2.6.7/css/style.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-table.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-bookdown.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-highlight.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-search.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-fontsettings.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-clipboard.css" rel="stylesheet" />


<link href="libs/anchor-sections-1.0.1/anchor-sections.css" rel="stylesheet" />
<script src="libs/anchor-sections-1.0.1/anchor-sections.js"></script>


<link rel="stylesheet" href="css/style.css" type="text/css" />
<link rel="stylesheet" href="css/prism.min.css" type="text/css" />
</head>

<body>


  <div class="book without-animation with-summary font-size-2 font-family-1" data-basepath=".">

    <div class="book-summary">
      <nav role="navigation">

<ul class="summary">
<li><a href="./" class="title">Introduction to Programming</a></li>

<li class="divider"></li>
<li class="chapter" data-level="" data-path="index.html"><a href="index.html"><i class="fa fa-check"></i>About this Book</a></li>
<li class="part"><span><b>I Python Basics</b></span></li>
<li class="chapter" data-level="1" data-path="python-intro.html"><a href="python-intro.html"><i class="fa fa-check"></i><b>1</b> Introduction to Python</a>
<ul>
<li class="chapter" data-level="1.1" data-path="python-intro.html"><a href="python-intro.html#programming-with-python"><i class="fa fa-check"></i><b>1.1</b> Programming with Python</a>
<ul>
<li class="chapter" data-level="1.1.1" data-path="python-intro.html"><a href="python-intro.html#versions"><i class="fa fa-check"></i><b>1.1.1</b> Versions</a></li>
</ul></li>
<li class="chapter" data-level="1.2" data-path="python-intro.html"><a href="python-intro.html#running-python-code"><i class="fa fa-check"></i><b>1.2</b> Running Python Code</a>
<ul>
<li class="chapter" data-level="1.2.1" data-path="python-intro.html"><a href="python-intro.html#jupyter-notebooks"><i class="fa fa-check"></i><b>1.2.1</b> Jupyter Notebooks</a></li>
<li class="chapter" data-level="1.2.2" data-path="python-intro.html"><a href="python-intro.html#on-the-command-line"><i class="fa fa-check"></i><b>1.2.2</b> On the Command Line</a></li>
</ul></li>
<li class="chapter" data-level="1.3" data-path="python-intro.html"><a href="python-intro.html#comments"><i class="fa fa-check"></i><b>1.3</b> Comments</a></li>
<li class="chapter" data-level="1.4" data-path="python-intro.html"><a href="python-intro.html#variables"><i class="fa fa-check"></i><b>1.4</b> Variables</a>
<ul>
<li class="chapter" data-level="1.4.1" data-path="python-intro.html"><a href="python-intro.html#data-types"><i class="fa fa-check"></i><b>1.4.1</b> Data Types</a></li>
</ul></li>
<li class="chapter" data-level="1.5" data-path="python-intro.html"><a href="python-intro.html#getting-help"><i class="fa fa-check"></i><b>1.5</b> Getting Help</a></li>
<li class="chapter" data-level="" data-path="python-intro.html"><a href="python-intro.html#resources"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="2" data-path="functions.html"><a href="functions.html"><i class="fa fa-check"></i><b>2</b> Functions</a>
<ul>
<li class="chapter" data-level="2.1" data-path="functions.html"><a href="functions.html#what-are-functions"><i class="fa fa-check"></i><b>2.1</b> What are Functions?</a></li>
<li class="chapter" data-level="2.2" data-path="functions.html"><a href="functions.html#python-function-syntax"><i class="fa fa-check"></i><b>2.2</b> Python Function Syntax</a>
<ul>
<li class="chapter" data-level="2.2.1" data-path="functions.html"><a href="functions.html#object-methods"><i class="fa fa-check"></i><b>2.2.1</b> Object Methods</a></li>
</ul></li>
<li class="chapter" data-level="2.3" data-path="functions.html"><a href="functions.html#built-in-python-functions"><i class="fa fa-check"></i><b>2.3</b> Built-in Python Functions</a>
<ul>
<li class="chapter" data-level="2.3.1" data-path="functions.html"><a href="functions.html#modules-and-libraries"><i class="fa fa-check"></i><b>2.3.1</b> Modules and Libraries</a></li>
</ul></li>
<li class="chapter" data-level="2.4" data-path="functions.html"><a href="functions.html#writing-functions"><i class="fa fa-check"></i><b>2.4</b> Writing Functions</a>
<ul>
<li class="chapter" data-level="2.4.1" data-path="functions.html"><a href="functions.html#doc-strings"><i class="fa fa-check"></i><b>2.4.1</b> Doc Strings</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="functions.html"><a href="functions.html#resources-1"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="3" data-path="logic.html"><a href="logic.html"><i class="fa fa-check"></i><b>3</b> Logic and Conditionals</a>
<ul>
<li class="chapter" data-level="3.1" data-path="logic.html"><a href="logic.html#booleans"><i class="fa fa-check"></i><b>3.1</b> Booleans</a>
<ul>
<li class="chapter" data-level="3.1.1" data-path="logic.html"><a href="logic.html#relational-operators"><i class="fa fa-check"></i><b>3.1.1</b> Relational Operators</a></li>
<li class="chapter" data-level="3.1.2" data-path="logic.html"><a href="logic.html#boolean-operators"><i class="fa fa-check"></i><b>3.1.2</b> Boolean Operators</a></li>
</ul></li>
<li class="chapter" data-level="3.2" data-path="logic.html"><a href="logic.html#conditional-statements"><i class="fa fa-check"></i><b>3.2</b> Conditional Statements</a>
<ul>
<li class="chapter" data-level="3.2.1" data-path="logic.html"><a href="logic.html#designing-conditions"><i class="fa fa-check"></i><b>3.2.1</b> Designing Conditions</a></li>
</ul></li>
<li class="chapter" data-level="3.3" data-path="logic.html"><a href="logic.html#determining-module-or-script"><i class="fa fa-check"></i><b>3.3</b> Determining Module or Script</a></li>
<li class="chapter" data-level="" data-path="logic.html"><a href="logic.html#resources-2"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="4" data-path="lists.html"><a href="lists.html"><i class="fa fa-check"></i><b>4</b> Lists and Sequences</a>
<ul>
<li class="chapter" data-level="4.1" data-path="lists.html"><a href="lists.html#what-is-a-list"><i class="fa fa-check"></i><b>4.1</b> What is a List?</a></li>
<li class="chapter" data-level="4.2" data-path="lists.html"><a href="lists.html#list-indices"><i class="fa fa-check"></i><b>4.2</b> List Indices</a></li>
<li class="chapter" data-level="4.3" data-path="lists.html"><a href="lists.html#list-operations-and-methods"><i class="fa fa-check"></i><b>4.3</b> List Operations and Methods</a></li>
<li class="chapter" data-level="4.4" data-path="lists.html"><a href="lists.html#nested-lists"><i class="fa fa-check"></i><b>4.4</b> Nested Lists</a></li>
<li class="chapter" data-level="4.5" data-path="lists.html"><a href="lists.html#other-sequences"><i class="fa fa-check"></i><b>4.5</b> Other Sequences</a>
<ul>
<li class="chapter" data-level="4.5.1" data-path="lists.html"><a href="lists.html#ranges"><i class="fa fa-check"></i><b>4.5.1</b> Ranges</a></li>
<li class="chapter" data-level="4.5.2" data-path="lists.html"><a href="lists.html#tuples"><i class="fa fa-check"></i><b>4.5.2</b> Tuples</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="lists.html"><a href="lists.html#resources-3"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="5" data-path="loops.html"><a href="loops.html"><i class="fa fa-check"></i><b>5</b> Iterating with Loops</a>
<ul>
<li class="chapter" data-level="5.1" data-path="loops.html"><a href="loops.html#for-loops"><i class="fa fa-check"></i><b>5.1</b> For Loops</a>
<ul>
<li class="chapter" data-level="5.1.1" data-path="loops.html"><a href="loops.html#variables-and-loops"><i class="fa fa-check"></i><b>5.1.1</b> Variables and Loops</a></li>
</ul></li>
<li class="chapter" data-level="5.2" data-path="loops.html"><a href="loops.html#lists-and-loops"><i class="fa fa-check"></i><b>5.2</b> Lists and Loops</a></li>
<li class="chapter" data-level="5.3" data-path="loops.html"><a href="loops.html#nested-loops"><i class="fa fa-check"></i><b>5.3</b> Nested Loops</a></li>
<li class="chapter" data-level="5.4" data-path="loops.html"><a href="loops.html#list-comprehensions"><i class="fa fa-check"></i><b>5.4</b> List Comprehensions</a></li>
<li class="chapter" data-level="5.5" data-path="loops.html"><a href="loops.html#while-loops"><i class="fa fa-check"></i><b>5.5</b> While Loops</a>
<ul>
<li class="chapter" data-level="5.5.1" data-path="loops.html"><a href="loops.html#counting-with-while-loops"><i class="fa fa-check"></i><b>5.5.1</b> Counting with While Loops</a></li>
<li class="chapter" data-level="5.5.2" data-path="loops.html"><a href="loops.html#sentinels"><i class="fa fa-check"></i><b>5.5.2</b> Sentinels</a></li>
<li class="chapter" data-level="5.5.3" data-path="loops.html"><a href="loops.html#difference-between-for-and-while-loops"><i class="fa fa-check"></i><b>5.5.3</b> Difference Between For and While Loops</a></li>
</ul></li>
<li class="chapter" data-level="5.6" data-path="loops.html"><a href="loops.html#iterating-over-files"><i class="fa fa-check"></i><b>5.6</b> Iterating over Files</a>
<ul>
<li class="chapter" data-level="5.6.1" data-path="loops.html"><a href="loops.html#tryexcept"><i class="fa fa-check"></i><b>5.6.1</b> Try/Except</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="loops.html"><a href="loops.html#resources-4"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="6" data-path="dictionaries.html"><a href="dictionaries.html"><i class="fa fa-check"></i><b>6</b> Dictionaries</a>
<ul>
<li class="chapter" data-level="6.1" data-path="dictionaries.html"><a href="dictionaries.html#what-is-a-dictionary"><i class="fa fa-check"></i><b>6.1</b> What is a Dictionary?</a></li>
<li class="chapter" data-level="6.2" data-path="dictionaries.html"><a href="dictionaries.html#accessing-a-dictionary"><i class="fa fa-check"></i><b>6.2</b> Accessing a Dictionary</a></li>
<li class="chapter" data-level="6.3" data-path="dictionaries.html"><a href="dictionaries.html#dictionary-methods"><i class="fa fa-check"></i><b>6.3</b> Dictionary Methods</a></li>
<li class="chapter" data-level="6.4" data-path="dictionaries.html"><a href="dictionaries.html#nesting-dictionaries"><i class="fa fa-check"></i><b>6.4</b> Nesting Dictionaries</a></li>
<li class="chapter" data-level="6.5" data-path="dictionaries.html"><a href="dictionaries.html#dictionaries-and-loops"><i class="fa fa-check"></i><b>6.5</b> Dictionaries and Loops</a>
<ul>
<li class="chapter" data-level="6.5.1" data-path="dictionaries.html"><a href="dictionaries.html#dictionary-comprehensions"><i class="fa fa-check"></i><b>6.5.1</b> Dictionary Comprehensions</a></li>
</ul></li>
<li class="chapter" data-level="6.6" data-path="dictionaries.html"><a href="dictionaries.html#which-data-structure-do-i-use"><i class="fa fa-check"></i><b>6.6</b> Which Data Structure Do I Use?</a></li>
<li class="chapter" data-level="" data-path="dictionaries.html"><a href="dictionaries.html#resources-5"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="7" data-path="searching.html"><a href="searching.html"><i class="fa fa-check"></i><b>7</b> Searching and Filtering</a>
<ul>
<li class="chapter" data-level="7.1" data-path="searching.html"><a href="searching.html#linear-search"><i class="fa fa-check"></i><b>7.1</b> Linear Search</a>
<ul>
<li class="chapter" data-level="7.1.1" data-path="searching.html"><a href="searching.html#maximal-search"><i class="fa fa-check"></i><b>7.1.1</b> Maximal Search</a></li>
<li class="chapter" data-level="7.1.2" data-path="searching.html"><a href="searching.html#falsification-search"><i class="fa fa-check"></i><b>7.1.2</b> Falsification Search</a></li>
</ul></li>
<li class="chapter" data-level="7.2" data-path="searching.html"><a href="searching.html#filtering"><i class="fa fa-check"></i><b>7.2</b> Filtering</a></li>
<li class="chapter" data-level="7.3" data-path="searching.html"><a href="searching.html#mapping"><i class="fa fa-check"></i><b>7.3</b> Mapping</a></li>
<li class="chapter" data-level="7.4" data-path="searching.html"><a href="searching.html#search-efficiency"><i class="fa fa-check"></i><b>7.4</b> Search Efficiency</a>
<ul>
<li class="chapter" data-level="7.4.1" data-path="searching.html"><a href="searching.html#linear-search-speed"><i class="fa fa-check"></i><b>7.4.1</b> Linear Search Speed</a></li>
<li class="chapter" data-level="7.4.2" data-path="searching.html"><a href="searching.html#faster-searching-binary-search"><i class="fa fa-check"></i><b>7.4.2</b> Faster Searching: Binary Search</a></li>
<li class="chapter" data-level="7.4.3" data-path="searching.html"><a href="searching.html#slower-algorithms-sorting"><i class="fa fa-check"></i><b>7.4.3</b> Slower Algorithms: Sorting</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="searching.html"><a href="searching.html#resources-6"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="8" data-path="functional-programming.html"><a href="functional-programming.html"><i class="fa fa-check"></i><b>8</b> Functional Programming</a>
<ul>
<li class="chapter" data-level="8.1" data-path="functional-programming.html"><a href="functional-programming.html#functions-are-variables"><i class="fa fa-check"></i><b>8.1</b> Functions ARE Variables</a>
<ul>
<li class="chapter" data-level="8.1.1" data-path="functional-programming.html"><a href="functional-programming.html#lambdas-anonymous-functions"><i class="fa fa-check"></i><b>8.1.1</b> lambdas: Anonymous Functions</a></li>
</ul></li>
<li class="chapter" data-level="8.2" data-path="functional-programming.html"><a href="functional-programming.html#functional-looping"><i class="fa fa-check"></i><b>8.2</b> Functional Looping</a>
<ul>
<li class="chapter" data-level="8.2.1" data-path="functional-programming.html"><a href="functional-programming.html#map"><i class="fa fa-check"></i><b>8.2.1</b> Map</a></li>
<li class="chapter" data-level="8.2.2" data-path="functional-programming.html"><a href="functional-programming.html#filter"><i class="fa fa-check"></i><b>8.2.2</b> Filter</a></li>
<li class="chapter" data-level="8.2.3" data-path="functional-programming.html"><a href="functional-programming.html#reduce"><i class="fa fa-check"></i><b>8.2.3</b> Reduce</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="functional-programming.html"><a href="functional-programming.html#resources-7"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="part"><span><b>II Specific Libraries</b></span></li>
<li class="chapter" data-level="9" data-path="pandas.html"><a href="pandas.html"><i class="fa fa-check"></i><b>9</b> The <code>pandas</code> Library</a>
<ul>
<li class="chapter" data-level="9.1" data-path="pandas.html"><a href="pandas.html#setting-up-pandas"><i class="fa fa-check"></i><b>9.1</b> Setting up <code>pandas</code></a></li>
<li class="chapter" data-level="9.2" data-path="pandas.html"><a href="pandas.html#series"><i class="fa fa-check"></i><b>9.2</b> Series</a>
<ul>
<li class="chapter" data-level="9.2.1" data-path="pandas.html"><a href="pandas.html#series-operations"><i class="fa fa-check"></i><b>9.2.1</b> Series Operations</a></li>
<li class="chapter" data-level="9.2.2" data-path="pandas.html"><a href="pandas.html#series-methods"><i class="fa fa-check"></i><b>9.2.2</b> Series Methods</a></li>
<li class="chapter" data-level="9.2.3" data-path="pandas.html"><a href="pandas.html#series-indexing"><i class="fa fa-check"></i><b>9.2.3</b> Series Indexing</a></li>
</ul></li>
<li class="chapter" data-level="9.3" data-path="pandas.html"><a href="pandas.html#dataframes"><i class="fa fa-check"></i><b>9.3</b> DataFrames</a>
<ul>
<li class="chapter" data-level="9.3.1" data-path="pandas.html"><a href="pandas.html#dataframe-operations"><i class="fa fa-check"></i><b>9.3.1</b> DataFrame Operations</a></li>
<li class="chapter" data-level="9.3.2" data-path="pandas.html"><a href="pandas.html#dataframe-methods"><i class="fa fa-check"></i><b>9.3.2</b> DataFrame Methods</a></li>
<li class="chapter" data-level="9.3.3" data-path="pandas.html"><a href="pandas.html#accessing-dataframes"><i class="fa fa-check"></i><b>9.3.3</b> Accessing DataFrames</a></li>
</ul></li>
<li class="chapter" data-level="9.4" data-path="pandas.html"><a href="pandas.html#grouping"><i class="fa fa-check"></i><b>9.4</b> Grouping</a>
<ul>
<li class="chapter" data-level="9.4.1" data-path="pandas.html"><a href="pandas.html#aggregation"><i class="fa fa-check"></i><b>9.4.1</b> Aggregation</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="pandas.html"><a href="pandas.html#resources-8"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="10" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html"><i class="fa fa-check"></i><b>10</b> Accessing Web APIs</a>
<ul>
<li class="chapter" data-level="10.1" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html#web-apis"><i class="fa fa-check"></i><b>10.1</b> Web APIs</a></li>
<li class="chapter" data-level="10.2" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html#restful-requests"><i class="fa fa-check"></i><b>10.2</b> RESTful Requests</a>
<ul>
<li class="chapter" data-level="10.2.1" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html#uris"><i class="fa fa-check"></i><b>10.2.1</b> URIs</a></li>
<li class="chapter" data-level="10.2.2" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html#http-verbs"><i class="fa fa-check"></i><b>10.2.2</b> HTTP Verbs</a></li>
</ul></li>
<li class="chapter" data-level="10.3" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html#accessing-web-apis-1"><i class="fa fa-check"></i><b>10.3</b> Accessing Web APIs</a></li>
<li class="chapter" data-level="10.4" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html#json-data"><i class="fa fa-check"></i><b>10.4</b> JSON Data</a></li>
<li class="chapter" data-level="" data-path="accessing-web-apis.html"><a href="accessing-web-apis.html#resources-9"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="appendix"><span><b>Appendix</b></span></li>
<li class="chapter" data-level="A" data-path="installing.html"><a href="installing.html"><i class="fa fa-check"></i><b>A</b> Installing Python</a>
<ul>
<li class="chapter" data-level="A.1" data-path="installing.html"><a href="installing.html#python"><i class="fa fa-check"></i><b>A.1</b> Python</a>
<ul>
<li class="chapter" data-level="A.1.1" data-path="installing.html"><a href="installing.html#anaconda"><i class="fa fa-check"></i><b>A.1.1</b> Anaconda</a></li>
</ul></li>
<li class="chapter" data-level="A.2" data-path="installing.html"><a href="installing.html#text-editors"><i class="fa fa-check"></i><b>A.2</b> Text Editors</a>
<ul>
<li class="chapter" data-level="A.2.1" data-path="installing.html"><a href="installing.html#visual-studio-code"><i class="fa fa-check"></i><b>A.2.1</b> Visual Studio Code</a></li>
<li class="chapter" data-level="A.2.2" data-path="installing.html"><a href="installing.html#atom"><i class="fa fa-check"></i><b>A.2.2</b> Atom</a></li>
<li class="chapter" data-level="A.2.3" data-path="installing.html"><a href="installing.html#sublime-text"><i class="fa fa-check"></i><b>A.2.3</b> Sublime Text</a></li>
<li class="chapter" data-level="A.2.4" data-path="installing.html"><a href="installing.html#pycharm"><i class="fa fa-check"></i><b>A.2.4</b> PyCharm</a></li>
</ul></li>
<li class="chapter" data-level="A.3" data-path="installing.html"><a href="installing.html#command-line-tools-bash"><i class="fa fa-check"></i><b>A.3</b> Command Line Tools (Bash)</a>
<ul>
<li class="chapter" data-level="A.3.1" data-path="installing.html"><a href="installing.html#command-line-on-a-mac"><i class="fa fa-check"></i><b>A.3.1</b> Command Line on a Mac</a></li>
<li class="chapter" data-level="A.3.2" data-path="installing.html"><a href="installing.html#command-line-on-windows"><i class="fa fa-check"></i><b>A.3.2</b> Command Line on Windows</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="installing.html"><a href="installing.html#resources-10"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="B" data-path="markdown.html"><a href="markdown.html"><i class="fa fa-check"></i><b>B</b> Markdown</a>
<ul>
<li class="chapter" data-level="B.1" data-path="markdown.html"><a href="markdown.html#writing-markdown"><i class="fa fa-check"></i><b>B.1</b> Writing Markdown</a>
<ul>
<li class="chapter" data-level="B.1.1" data-path="markdown.html"><a href="markdown.html#text-formatting"><i class="fa fa-check"></i><b>B.1.1</b> Text Formatting</a></li>
<li class="chapter" data-level="B.1.2" data-path="markdown.html"><a href="markdown.html#text-blocks"><i class="fa fa-check"></i><b>B.1.2</b> Text Blocks</a></li>
</ul></li>
<li class="chapter" data-level="B.2" data-path="markdown.html"><a href="markdown.html#rendering-markdown"><i class="fa fa-check"></i><b>B.2</b> Rendering Markdown</a></li>
<li class="chapter" data-level="" data-path="markdown.html"><a href="markdown.html#resources-11"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="C" data-path="command-line.html"><a href="command-line.html"><i class="fa fa-check"></i><b>C</b> The Command Line</a>
<ul>
<li class="chapter" data-level="C.1" data-path="command-line.html"><a href="command-line.html#accessing-the-command-line"><i class="fa fa-check"></i><b>C.1</b> Accessing the Command line</a></li>
<li class="chapter" data-level="C.2" data-path="command-line.html"><a href="command-line.html#navigating-the-command-line"><i class="fa fa-check"></i><b>C.2</b> Navigating the Command Line</a>
<ul>
<li class="chapter" data-level="C.2.1" data-path="command-line.html"><a href="command-line.html#changing-directories"><i class="fa fa-check"></i><b>C.2.1</b> Changing Directories</a></li>
<li class="chapter" data-level="C.2.2" data-path="command-line.html"><a href="command-line.html#listing-files"><i class="fa fa-check"></i><b>C.2.2</b> Listing Files</a></li>
<li class="chapter" data-level="C.2.3" data-path="command-line.html"><a href="command-line.html#paths"><i class="fa fa-check"></i><b>C.2.3</b> Paths</a></li>
</ul></li>
<li class="chapter" data-level="C.3" data-path="command-line.html"><a href="command-line.html#file-commands"><i class="fa fa-check"></i><b>C.3</b> File Commands</a>
<ul>
<li class="chapter" data-level="C.3.1" data-path="command-line.html"><a href="command-line.html#learning-new-commands"><i class="fa fa-check"></i><b>C.3.1</b> Learning New Commands</a></li>
<li class="chapter" data-level="C.3.2" data-path="command-line.html"><a href="command-line.html#wildcards"><i class="fa fa-check"></i><b>C.3.2</b> Wildcards</a></li>
</ul></li>
<li class="chapter" data-level="C.4" data-path="command-line.html"><a href="command-line.html#dealing-with-errors"><i class="fa fa-check"></i><b>C.4</b> Dealing With Errors</a></li>
<li class="chapter" data-level="C.5" data-path="command-line.html"><a href="command-line.html#directing-output"><i class="fa fa-check"></i><b>C.5</b> Directing Output</a></li>
<li class="chapter" data-level="C.6" data-path="command-line.html"><a href="command-line.html#shell-scripts"><i class="fa fa-check"></i><b>C.6</b> Shell Scripts</a></li>
<li class="chapter" data-level="" data-path="command-line.html"><a href="command-line.html#resources-12"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="chapter" data-level="D" data-path="javascript.html"><a href="javascript.html"><i class="fa fa-check"></i><b>D</b> JavaScript</a>
<ul>
<li class="chapter" data-level="D.1" data-path="javascript.html"><a href="javascript.html#programming-with-javascript"><i class="fa fa-check"></i><b>D.1</b> Programming with JavaScript</a>
<ul>
<li class="chapter" data-level="D.1.1" data-path="javascript.html"><a href="javascript.html#history-and-versions"><i class="fa fa-check"></i><b>D.1.1</b> History and Versions</a></li>
<li class="chapter" data-level="D.1.2" data-path="javascript.html"><a href="javascript.html#running-javascript"><i class="fa fa-check"></i><b>D.1.2</b> Running JavaScript</a></li>
</ul></li>
<li class="chapter" data-level="D.2" data-path="javascript.html"><a href="javascript.html#javascript-basics"><i class="fa fa-check"></i><b>D.2</b> JavaScript Basics</a>
<ul>
<li class="chapter" data-level="D.2.1" data-path="javascript.html"><a href="javascript.html#strict-mode"><i class="fa fa-check"></i><b>D.2.1</b> Strict Mode</a></li>
</ul></li>
<li class="chapter" data-level="D.3" data-path="javascript.html"><a href="javascript.html#variables-1"><i class="fa fa-check"></i><b>D.3</b> Variables</a>
<ul>
<li class="chapter" data-level="D.3.1" data-path="javascript.html"><a href="javascript.html#basic-data-types"><i class="fa fa-check"></i><b>D.3.1</b> Basic Data Types</a></li>
<li class="chapter" data-level="D.3.2" data-path="javascript.html"><a href="javascript.html#type-coercion"><i class="fa fa-check"></i><b>D.3.2</b> Type Coercion</a></li>
<li class="chapter" data-level="D.3.3" data-path="javascript.html"><a href="javascript.html#arrays"><i class="fa fa-check"></i><b>D.3.3</b> Arrays</a></li>
<li class="chapter" data-level="D.3.4" data-path="javascript.html"><a href="javascript.html#objects"><i class="fa fa-check"></i><b>D.3.4</b> Objects</a></li>
</ul></li>
<li class="chapter" data-level="D.4" data-path="javascript.html"><a href="javascript.html#control-structures"><i class="fa fa-check"></i><b>D.4</b> Control Structures</a>
<ul>
<li class="chapter" data-level="D.4.1" data-path="javascript.html"><a href="javascript.html#conditionals"><i class="fa fa-check"></i><b>D.4.1</b> Conditionals</a></li>
<li class="chapter" data-level="D.4.2" data-path="javascript.html"><a href="javascript.html#loops-1"><i class="fa fa-check"></i><b>D.4.2</b> Loops</a></li>
</ul></li>
<li class="chapter" data-level="D.5" data-path="javascript.html"><a href="javascript.html#functions-1"><i class="fa fa-check"></i><b>D.5</b> Functions</a>
<ul>
<li class="chapter" data-level="D.5.1" data-path="javascript.html"><a href="javascript.html#functional-programming-1"><i class="fa fa-check"></i><b>D.5.1</b> Functional Programming</a></li>
</ul></li>
<li class="chapter" data-level="" data-path="javascript.html"><a href="javascript.html#resources-13"><i class="fa fa-check"></i>Resources</a></li>
</ul></li>
<li class="divider"></li>
<li><a href="https://github.com/rstudio/bookdown" target="blank">Published with bookdown</a></li>

</ul>

      </nav>
    </div>

    <div class="book-body">
      <div class="body-inner">
        <div class="book-header" role="navigation">
          <h1>
            <i class="fa fa-circle-o-notch fa-spin"></i><a href="./">Introduction to Programming</a>
          </h1>
        </div>

        <div class="page-wrapper" tabindex="-1" role="main">
          <div class="page-inner">

            <section class="normal" id="section-">
<div id="searching" class="section level1" number="7">
<h1><span class="header-section-number">Chapter 7</span> Searching and Filtering</h1>
<p>One of the most common and important uses of computer programs is to <strong>search</strong> a large set of data for a specific record or observation—indeed, a significant portion of what computers <em>do</em> is search through data. This chapter covers a number of common <em>patterns</em> and <em>algorithms</em> used when searching through lists of data in order to answer questions about that data. Note that this chapter introduces no new syntax, but instead provides a deeper look at using <em>loops</em> and <em>lists</em>. The first two sections illustrates common interactions with lists, while the last considers at a high level the efficiency of algorithms.</p>
<div id="linear-search" class="section level2" number="7.1">
<h2><span class="header-section-number">7.1</span> Linear Search</h2>
<p>Fundamentally, search algorithms are used to “find” a particular item in list: given a very large list of elements, the goal of the search is to determine <em>whether</em> the list contains the “target” item, and if so <em>where</em> in the list that element is. Thus basic search algorithms are used to answer the questions <strong><em>is an item in a list?</em></strong> or <em><strong>which element in the list is the item?</strong></em>.</p>
<div class="alert alert-info">
<p>Python does contain built-in operators and list methods (e.g., <code>in</code>, <code>index()</code>, <code>max()</code> etc.) that can answer simple versions of these questions. However, more complex programs may require you to create your own “custom” searches following the patterns described here.</p>
</div>
<p>The most basic algorithm you can use to answer these questions is called a <strong>linear search</strong>. Intuitively, this search takes all of the elements in a list, and then goes down the “line” of elements one after another, <em>checking</em> if each element in turn is the target item. (Think: “Are you who I’m looking for?” “No” “Are you who I’m looking for?” “No”, “Are you who I’m looking for?” “Yes!”). If you get through the entire line of items <em>without</em> finding the target (without anyone answering “yes”), then you know that the target is not in the list (because you checked everyone)!</p>
<p>This kind of search involves just a simple <code>for</code> loop (to consider every element) and <code>if</code> statement (to check if the item is the target):</p>
<pre class="language-python"><code><span class="token keyword">def</span> <span class="token function">linear_in</span><span class="token punctuation">(</span>a_list<span class="token punctuation">,</span> target<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token triple-quoted-string string">"""Searches the given list for the given target value.
       Returns whether or not the target is in the list"""</span>

    <span class="token keyword">for</span> element <span class="token keyword">in</span> a_list<span class="token punctuation">:</span>     <span class="token comment"># go through each element</span>
        <span class="token keyword">if</span> element <span class="token operator">==</span> target<span class="token punctuation">:</span>  <span class="token comment"># check that element</span>
            <span class="token keyword">return</span> <span class="token boolean">True</span>        <span class="token comment"># if found, report so!</span>

    <span class="token keyword">return</span> <span class="token boolean">False</span>  <span class="token comment"># looked at everyone but didn't find, report back</span>

<span class="token comment"># Example:</span>
numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">17</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span>  <span class="token comment"># the list to search</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> linear_in<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>  <span class="token comment"># True, 11 in list</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> linear_in<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>  <span class="token comment"># False, 12 not in list</span></code></pre>
<p>Pay careful attention to the position of the <code>return</code> statements! First, you return <code>True</code> if (when) the target is found—this “exits” the function so you do not keep searching once you’ve found your target. The second <code>return</code> statement occurs <em>after the loop has entirely finished</em>. You need to check <em>every</em> item in the list before you can conclusively say that the item isn’t there (otherwise you may have just missed it).</p>
<p>A common error is include an <code>else</code> clause that returns or stores that the item was not found. However, returning <code>False</code> makes the statement “<strong>none</strong> of the elements in the list is the target” which is dependent on the entire list: looking at a single item won’t let you make that claim! Contrast this with returning <code>True</code>, which makes the statement “<strong>one</strong> of the elements in the list is the target”, which can be proved by considering just one item (e.g., the <em>one</em>).</p>
<p>While a useful organizing tool, a linear search does not need to be implemented as its own function if you instead use a variable to track whether the item is found or not:</p>
<pre class="language-python"><code>is_found <span class="token operator">=</span> <span class="token boolean">False</span>  <span class="token comment"># has not been found when we start looking</span>
<span class="token keyword">for</span> element <span class="token keyword">in</span> a_list<span class="token punctuation">:</span>   <span class="token comment"># go through each element</span>
  <span class="token keyword">if</span> element <span class="token operator">==</span> target<span class="token punctuation">:</span>  <span class="token comment"># check that element</span>
      is_found <span class="token operator">=</span> <span class="token boolean">True</span>       <span class="token comment"># mark as found!</span></code></pre>
<p>To determine <strong>which</strong> element in the list is the target, you use the same structure but consider the <em>index</em> of each element, returning that index when the item is found. By convention, if the target is <em>not</em> in the list, you can return <code>-1</code> (which will be an out-of-bounds index for any list):</p>
<pre class="language-python"><code><span class="token keyword">def</span> <span class="token function">linear_search</span><span class="token punctuation">(</span>a_list<span class="token punctuation">,</span> target<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token triple-quoted-string string">"""Searches the given list for the given target value.
       Returns the index of the target, or -1 if target not in the list"""</span>

    <span class="token keyword">for</span> index <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span><span class="token builtin">len</span><span class="token punctuation">(</span>a_list<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>  <span class="token comment"># go through each element</span>
        <span class="token keyword">if</span> a_list<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token operator">==</span> target<span class="token punctuation">:</span>  <span class="token comment"># check that element</span>
            <span class="token keyword">return</span> index  <span class="token comment"># if found, report the index</span>

    <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>  <span class="token comment"># looked at everyone but didn't find, report back</span>

<span class="token comment"># Example:</span>
numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">17</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span> <span class="token comment"># the list to search</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> linear_search<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>  <span class="token comment"># 4</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> linear_search<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>  <span class="token comment"># -1</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> linear_search<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">)</span> <span class="token operator">>=</span> <span class="token number">0</span> <span class="token punctuation">)</span>  <span class="token comment"># True, 11 in list</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> linear_search<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">)</span> <span class="token operator">>=</span> <span class="token number">0</span> <span class="token punctuation">)</span>  <span class="token comment"># False, 12 not in list</span></code></pre>
<div id="maximal-search" class="section level3" number="7.1.1">
<h3><span class="header-section-number">7.1.1</span> Maximal Search</h3>
<p>Another common item to search for is the “biggest” (or “smallest”) element in the list. This may be the biggest number, the longest word, the slowest turtle, the highest-scoring sports game… any element that has a “greater” ordinal value (e.g., it comes “first” in some ordered listing, whether that ordering is <em>ascending</em> or <em>descending</em>). Whenever you are searching for the “-est” item in a list, you can use the same variant on a linear search.</p>
<p>I refer to this variant as a “king-of-the-hill” search, named after the <a href="https://en.wikipedia.org/wiki/King_of_the_Hill_(game)">children’s game</a>. In this algorithm, start by declaring an initial element (often the first in the list) as the “king”—the “greatest” value in the list. The algorithm then goes down the “line” of elements, having each one in turn “challenge” the king. If the challenging value is greater, then that value becomes the new king, and the process continues. Whichever item is the king at the end must be the “greatest” item that was being searched for.</p>
<p>This algorithm is implemented with a similar structure to the basic linear search, except instead of comparing to the target, you compare to the current “king”:</p>
<pre class="language-python"><code><span class="token keyword">def</span> <span class="token function">maximum</span><span class="token punctuation">(</span>a_list<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token triple-quoted-string string">"""Returns the element with the maximum value in the list."""</span>

    maximum <span class="token operator">=</span> a_list<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>  <span class="token comment"># first person starts as the "king"</span>
    <span class="token keyword">for</span> element <span class="token keyword">in</span> a_list<span class="token punctuation">:</span>  <span class="token comment"># go through each element</span>
        <span class="token keyword">if</span> element <span class="token operator">></span> maximum<span class="token punctuation">:</span>  <span class="token comment"># challenge the king</span>
            maximum <span class="token operator">=</span> element  <span class="token comment"># if won, become the new king</span>

    <span class="token keyword">return</span> maximum  <span class="token comment"># in the end, return who is left standing</span>

<span class="token comment"># Example:</span>
numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">17</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span> <span class="token comment"># the list to search</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> maximum<span class="token punctuation">(</span>numbers<span class="token punctuation">)</span> <span class="token punctuation">)</span>  <span class="token comment"># 18</span></code></pre>
<div class="alert alert-warning">
<p>The most common error with this algorithm is not comparing to the <em>previous maximum</em>, instead trying to compare to e.g, the previous element in the list.</p>
</div>
<div class="alert alert-info">
<p>Note that it is also possible to do this same search by using the built-in <code>max()</code> function and specifying an <em>ordering function</em> as an argument, which converts any element into a value with the proper ordering. Using functions as arguments is discussed in a later chapter.</p>
</div>
<p>To reiterate, this function can be used to find any extreme value simply by changing the “challenge” comparison. For example use <code>&lt;</code> instead of <code>&gt;</code> to find the “minimum” item, or use a more complex boolean expression to compare dictionary “rows” in a data table.</p>
</div>
<div id="falsification-search" class="section level3" number="7.1.2">
<h3><span class="header-section-number">7.1.2</span> Falsification Search</h3>
<p>Many searches are interested in determining if <em>all</em> elements in a list meet a certain criteria. For example, determining if all the numbers are greater than 10, if all of the words are less than 3 syllables, if all of the turtles are running at speed, or if the home team won all of their games.</p>
<p>But loops are only able to consider one element at a time, not “all” the elements at once. So in order to answer these questions, you need to <strong>invert</strong> the question: saying “<em>all</em> numbers are <em>greater</em> than 10” is logically equivalent to saying “<em>no</em> number is <em>less</em> than (or equal to) 10”.</p>
<p class="alert alert-info">
(Somewhat counter-intuitively, the logical negation of an <em>“all are”</em> predicate is not <em>“none are”</em> but <em>“<strong>one</strong> is not”</em>). That is, the opposite of “all days are sunny” is not “no days are sunny” but “(at least) one day was not sunny”.
</p>
<p>By inverting the question into a search for a <strong>counter-example</strong>, you can utilize the previous linear search pattern:</p>
<pre class="language-python"><code><span class="token keyword">def</span> <span class="token function">all_larger</span><span class="token punctuation">(</span>a_list<span class="token punctuation">,</span> minimum<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token triple-quoted-string string">"""Returns whether all of the elements in the list are larger than the
       given minimum value."""</span>

    all_are_large <span class="token operator">=</span> <span class="token boolean">True</span>  <span class="token comment"># every number we've looked at is large</span>
    <span class="token keyword">for</span> element <span class="token keyword">in</span> a_list<span class="token punctuation">:</span>
       <span class="token keyword">if</span> <span class="token keyword">not</span> <span class="token punctuation">(</span>element <span class="token operator">></span> minimum<span class="token punctuation">)</span><span class="token punctuation">:</span>  <span class="token comment"># written as counter-example</span>
                                    <span class="token comment"># equivalent to `element &lt;= minimum`</span>
           all_are_large <span class="token operator">=</span> <span class="token boolean">False</span>  <span class="token comment"># counterexample found! Statement no longer valid</span>
           <span class="token keyword">break</span>  <span class="token comment"># "exits" from the loop, since don't need to search more</span>

    <span class="token keyword">return</span> all_are_large  <span class="token comment"># report back</span>

<span class="token comment"># Example:</span>
numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">17</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span> <span class="token comment"># the list to search</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> all_larger<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>  <span class="token comment"># False, some numbers are smaller than 10</span>
<span class="token keyword">print</span><span class="token punctuation">(</span> all_larger<span class="token punctuation">(</span>numbers<span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>  <span class="token comment"># True, all numbers are greater than 2</span></code></pre>
<p class="alert alert-success">
Careful variable naming (e.g., <code>all_are_large</code>) for keeping track of boolean claims is vital to being able to read and write these algorithms! Just calling the variable e.g., <code>large</code> can make it confusing to understand what your logic is doing.
</p>
<p>Overall, a linear search is a simple and versatile algorithm, but you need to be careful to use the right variation based on the question being asked.</p>
</div>
</div>
<div id="filtering" class="section level2" number="7.2">
<h2><span class="header-section-number">7.2</span> Filtering</h2>
<p>In addition to searching data for a specific item, you will often want to search a data set for <em>all</em> items that meet some criteria. For example, you want to find all items numbers that are large, or all sports games that the home team one, or all outliers in a medical diagnoses. This is called <strong>filtering</strong> for a set of data. Filtering is one of the most common steps used in data analysis; indeed the searching described in the previous section can be seen as a specialized filtering (where you’re filtering for a single element).</p>
<p>Importantly, when we talk about filtering in programming, we think about what items we want to select or keep, rather than what items we want to discard. We don’t try to “filter out the small numbers”, instead we try to “filter (select) for the big numbers”. A filter is about what is let in (a <a href="https://www.schneier.com/blog/archives/2011/01/whitelisting_vs.html">whitelist</a>), not about what is excluded.</p>
<p>The simplest way to filter a data set is to use a loop similar to a linear search, but instead of finding a single element, you construct a <em>new</em> list that contains the elements that “pass” the filter and thus that you want to keep. This follows the basic template:</p>
<pre class="language-python"><code>result_list <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token comment"># initialize new list</span>
<span class="token keyword">for</span> value <span class="token keyword">in</span> original_sequence<span class="token punctuation">:</span> <span class="token comment"># loop through the items</span>
    <span class="token keyword">if</span> value meets criteria<span class="token punctuation">:</span> <span class="token comment"># if item "passes" the filter and should be kept</span>
        result_list<span class="token punctuation">.</span>append<span class="token punctuation">(</span>value<span class="token punctuation">)</span> <span class="token comment"># add value to new list</span></code></pre>
<p>As a concrete example, you can filter a list of numbers for those that are “large” (e.g., greater than 10):</p>
<pre class="language-python"><code>numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">17</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span> <span class="token comment"># the list to search</span>

large_numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token comment"># the list for the items to find</span>
<span class="token keyword">for</span> number <span class="token keyword">in</span> numbers<span class="token punctuation">:</span> <span class="token comment"># loop through the values</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>number <span class="token operator">></span> <span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token comment"># check if the value</span>
        large_numbers<span class="token punctuation">.</span>append<span class="token punctuation">(</span>number<span class="token punctuation">)</span>

<span class="token keyword">print</span><span class="token punctuation">(</span>large_numbers<span class="token punctuation">)</span> <span class="token comment"># [17, 18, 11, 16, 13]</span></code></pre>
<p>There are two important things to notice in this example.</p>
<p>First, filtering involves constructing a <em>new</em> list or sequence. This makes the code easier to write and process (you don’t need to worry about deleting things from the middle of a list), and is best practice in doing data analysis because you won’t modify or “lose” your original data, so that you can perform different filters on it (e.g., you could also filter for which numbers are even).</p>
<p>Second, the <code>if</code> statement’s expression checks if the value meets the desired criteria and should be added to the new list, not whether it should be skipped or removed. Filtering is a “positive” process. The filter criteria (the boolean expression) can be as complex as needed; you can check multiple criteria by using the <code>and</code> or <code>or</code> operators. And of course you can include additional statements or <code>if</code> statements if that helps make your code more understandable:</p>
<pre class="language-python"><code>i_words <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
<span class="token keyword">for</span> word <span class="token keyword">in</span> word_list<span class="token punctuation">:</span>
    lower_case_word <span class="token operator">=</span> word<span class="token punctuation">.</span>lower<span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token comment"># format for consideration</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>lower_case_word<span class="token punctuation">.</span>startswith<span class="token punctuation">(</span><span class="token string">'i'</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token comment"># check starting letter</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token keyword">not</span> lower_case_word <span class="token keyword">in</span> i_words<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token comment"># don't keep if already in list</span>
            chosen_words<span class="token punctuation">.</span>append<span class="token punctuation">(</span>word<span class="token punctuation">)</span> <span class="token comment"># keep original word</span></code></pre>
<p>Of course, to use a more Pythonic approach you can do filtering using a <em>list comprehension</em>:</p>
<pre class="language-python"><code>numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">17</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span> <span class="token comment"># the list to search</span>
large_nubmers <span class="token operator">=</span> <span class="token punctuation">[</span>number <span class="token keyword">for</span> number <span class="token keyword">in</span> numbers <span class="token keyword">if</span> number <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">]</span>
<span class="token keyword">print</span><span class="token punctuation">(</span>large_numbers<span class="token punctuation">)</span> <span class="token comment"># [17, 18, 11, 16, 13]</span></code></pre>
<p>Using an <code>if</code> statement in a list comprehensino performs a filtering operation!</p>
<p>Note that The <code>i_words</code> example cannot be written as a list comprehension, because the filtering work is dependent on the previous results—it is not considered a “pure” operation.</p>
<!-- Additionally, Python does provides a _built-in function_ called **`filter()`** that can be used to filter a list without needing to write a for loop. This function takes a list and produces a _new_ list that contains only the elements that _do match_ a specific criteria. The `filter()` function takes in two arguments: the first is a _callback function_ that will do check if the value should be kept, and the second is the list to filter. The callback function takes in a _single_ argument&mdash;an element to consider&mdash;and returns `True` if the element should be included in the filtered list or `False` otherwise. See the chapter on [#functional-programming](Functional Programming) for more details about callback functions (and lambdas like the one used in the below example). The `filter()` function also returns an _iterator_ rather than an actual list, so needs to be converted into a list to be used further.

```python
numbers = [2,7,1,8,3] # an initial list

evens = list(filter(lambda n: n % 2 == 0 , numbers))
print(evens) # [2, 8]
``` -->
</div>
<div id="mapping" class="section level2" number="7.3">
<h2><span class="header-section-number">7.3</span> Mapping</h2>
<p>You can’t talk about filtering without also mentioning its cousin, mapping. A <strong>mapping</strong> operation is one that takes an original list (e.g., of numbers) and produces a <em>new</em> list with each of the original elements transformed in a certain way (e.g., rounded). The operation “maps” each number into a new value in the new list. This is a common operation to apply: maybe you want to “transform” a list so that all the values are rounded or lowercase, or you want to map a list of words to a list of their lengths.</p>
<p>Mapping can be done using a similar looping process to filtering, but you add a transformed value to the new list (instead of the original value if it meets a filtering criteria):</p>
<pre class="language-python"><code>numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1.3</span><span class="token punctuation">,</span> <span class="token number">2.7</span><span class="token punctuation">,</span> <span class="token number">3.14</span><span class="token punctuation">,</span> <span class="token number">4.8</span><span class="token punctuation">,</span> <span class="token number">5.99</span><span class="token punctuation">]</span> <span class="token comment"># the list to map</span>
rounded_numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>  <span class="token comment"># a new list for the mapped values</span>
<span class="token keyword">for</span> number <span class="token keyword">in</span> numbers<span class="token punctuation">:</span> <span class="token comment"># loop through the original list</span>
    transformed <span class="token operator">=</span> <span class="token builtin">round</span><span class="token punctuation">(</span>number<span class="token punctuation">)</span> <span class="token comment"># map the individual item</span>
    rounded_numbers<span class="token punctuation">.</span>append<span class="token punctuation">(</span>transformed<span class="token punctuation">)</span> <span class="token comment"># add transformed value to new list.</span>

<span class="token keyword">print</span><span class="token punctuation">(</span>rounded_numbers<span class="token punctuation">)</span>  <span class="token comment"># [1, 3, 3, 5, 6]</span></code></pre>
<p>You might recognize this example—this kind of process is exactly what a <em>list comprehension</em> does! In fact, a list comprehension is a mapping operation—every comprehension is doing some kind of mapping (and likely some filtering at the same time):</p>
<pre class="language-python"><code>numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1.3</span><span class="token punctuation">,</span> <span class="token number">2.7</span><span class="token punctuation">,</span> <span class="token number">3.14</span><span class="token punctuation">,</span> <span class="token number">4.8</span><span class="token punctuation">,</span> <span class="token number">5.99</span><span class="token punctuation">]</span> <span class="token comment"># the list to map</span>
rounded_numbers <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token builtin">round</span><span class="token punctuation">(</span>number<span class="token punctuation">)</span> <span class="token keyword">for</span> number <span class="token keyword">in</span> numbers<span class="token punctuation">]</span>
<span class="token keyword">print</span><span class="token punctuation">(</span>rounded_numbers<span class="token punctuation">)</span>  <span class="token comment"># [1, 3, 3, 5, 6]</span></code></pre>
<!-- Additionally, Python also provides a _built-in function_ called **`map()`** can be used to map a list without writing an explicit loop or comprehension. Like with the `filter()` function, the `map()` function takes in two arguments: the first is a _callback function_ that will perform the mapping operation, and the second is the list to filter. The callback function takes in a _single_ argument&mdash;the element to map&mdash;and returns the transformed value. See the chapter on [#functional-programming](Functional Programming) for more details about callback functions (and lambdas like the one used in the below example). The `map()` function also returns an _iterator_ rather than an actual list, so needs to be converted into a list to be used further.

```python
numbers = [1.3, 2.7, 3.14, 4.8, 5.99] # the list to map
rounded_numbers = list(map(lambda number: round(number), numbers))
print(rounded_numbers)  # [1, 3, 3, 5, 6]
``` -->
</div>
<div id="search-efficiency" class="section level2" number="7.4">
<h2><span class="header-section-number">7.4</span> Search Efficiency</h2>
<p>Searching is something that you do a lot (and on bigger and bigger data sets!), so it’s worth considering: how fast is this process? How <em>efficient</em> is the algorithm? Is there possibly a more efficient way of searching?</p>
<p class="alert alert-danger">
<strong>Warning: <em>AVOID PRE-MATURE OPTIMIZATION</em>!!</strong> While this section and chapter discuss the “speed” of computer programs, you should avoid spending too much (or any!) time trying to make your program “as fast as possible”. The first step in any computer program is to make it function at all. Once you have it working, <em>then</em> you can worry about increasing the efficiency—and only if it is currently too slow for your purposes. Pre-mature optimization (trying to make it work fast before you make it work at all) is a major source of bugs and other problems.
</p>
<p>One way of measuring the speed of an algorithm would be to <em>time it</em>, such as by using a stopwatch. Python includes <a href="https://docs.python.org/3/library/time.html">modules</a> that can be used to record the time, allowing you to get the “start” and “stop” time of the algorithm, and then calculate the elapsed duration. However, this <strong>wall-clock efficiency</strong> is highly dependent on the exact list being searched and on the computer that is executing the algorithm—if you’re also streaming videos while searching, the algorithm may run slower!</p>
<p>Instead, computer scientists measure the efficiency of a program by counting the number of <em>operations</em> that the algorithm does. This number will be independent of the data and machine, and so makes it easier to compare approaches. Specifically, to measure the efficiency of a search, you would consider the number of <strong>comparisons</strong> that need to be made between elements (e.g., how many elements you check before you find what you’re looking for), under the assumption that this is the most time-consuming part of the computer’s search algorithm.</p>
<div id="linear-search-speed" class="section level3" number="7.4.1">
<h3><span class="header-section-number">7.4.1</span> Linear Search Speed</h3>
<p>Linear search involves looking at each item in the list one at a time, so the number of “checks” that need to be made is <em>dependent on the size of the list</em>. And because the item you’re looking for may be either be at the beginning of the list (meaning you don’t search for very long) or at the end, you can consider both the “average” case (when it’s in the middle), as well as the “worst” case (when it’s at the end or not in the list at all!):</p>
<table>
<thead>
<tr class="header">
<th align="left">len(list)</th>
<th align="left"># comparisons (avg)</th>
<th align="left"># comparisons (worst)</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td align="left">10</td>
<td align="left">5</td>
<td align="left">10</td>
</tr>
<tr class="even">
<td align="left">20</td>
<td align="left">10</td>
<td align="left">20</td>
</tr>
<tr class="odd">
<td align="left">50</td>
<td align="left">25</td>
<td align="left">50</td>
</tr>
<tr class="even">
<td align="left">100</td>
<td align="left">50</td>
<td align="left">100</td>
</tr>
<tr class="odd">
<td align="left">1000</td>
<td align="left">500</td>
<td align="left">1000</td>
</tr>
<tr class="even">
<td align="left"><strong><code>N</code></strong></td>
<td align="left"><strong><code>N/2</code></strong></td>
<td align="left"><strong><code>N</code></strong></td>
</tr>
</tbody>
</table>
<p>These numbers should be somewhat intuitive: because you’re looking at each element in a line, in the average case you need to look at half of the elements, and in the worst case you need to look at all of them! As such, the number of comparisons you need to make (and thus the efficiency of the algorithm) is a <strong>linear function</strong> of the size of the list:</p>
<div class="figure">
<img src="img/searching/linear-time.png" alt="" />
<p class="caption">Linear time complexity. Image by Nick Salloum.</p>
</div>
<p>This is in fact why it is called a <strong><em>linear</em></strong> search!</p>
<p>In general, we measure algorithm efficiency (or more properly, <strong>algorithmic complexity</strong>) in terms of the <em>rate of change</em> in the speed: that is, if you double the size of the input list, by what ratio does the work you need to do increase? With a linear search, doubling the size of the list will double the amount of work to do.</p>
<p>Note that looking up an element by its index or key is a <strong>constant function</strong>—it takes the same amount of time no matter how big the list or dictionary is. This is part of why dictionaries are so useful as look-up tables: you don’t need to spend time searching for the value if it you have its key!</p>
</div>
<div id="faster-searching-binary-search" class="section level3" number="7.4.2">
<h3><span class="header-section-number">7.4.2</span> Faster Searching: Binary Search</h3>
<p>There are alternate, faster algorithms for searching through lists that can be useful as the data set gets large.</p>
<p>As an example, consider how you might search for a name in a phone book (or a word in an encyclopedia): rather than starting from “A” and going one by one though the book, you flip it open to the middle. If the name you’re after comes later in the alphabet than the page you opened to, then you take the “back half” of the book and flip to the middle of that (otherwise, you flip to the middle of the “front half”). You repeat this process, narrowing the number of pages you need to consider more and more until you’ve found the name you are looking for!</p>
<p>What makes this work is the fact that names in the phone book are <strong>ordered</strong>: after doing a comparison (checking the name against the page), you know whether to go forward or backwards to find the target.</p>
<p>This algorithm is known as a <strong>binary search</strong>, and it lets you search an <em>ordered</em> list by comparing to the middle, and reducing the list to only the top or bottom half, and repeating:</p>
<pre class="language-python"><code><span class="token keyword">def</span> <span class="token function">binary_search</span><span class="token punctuation">(</span>a_list<span class="token punctuation">,</span> target<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token triple-quoted-string string">"""Searches the given SORTED list for the given target value.
       Returns the index of the target, or -1 if target not in the list"""</span>

    start_index <span class="token operator">=</span> <span class="token number">0</span> <span class="token comment"># initial goalposts</span>
    end_index <span class="token operator">=</span> <span class="token builtin">len</span><span class="token punctuation">(</span>a_list<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span>

    <span class="token keyword">while</span> start_index <span class="token operator">&lt;=</span> end_index<span class="token punctuation">:</span>  <span class="token comment"># at least one thing to look at</span>
        middle_index <span class="token operator">=</span> <span class="token punctuation">(</span>start_index <span class="token operator">+</span> end_index<span class="token punctuation">)</span> <span class="token operator">//</span> <span class="token number">2</span>  <span class="token comment"># middle (integer) index</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>a_list<span class="token punctuation">[</span>middle_index<span class="token punctuation">]</span> <span class="token operator">==</span> target<span class="token punctuation">)</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> middle_index  <span class="token comment"># found the item!</span>
        <span class="token keyword">elif</span> target <span class="token operator">></span> a_list<span class="token punctuation">[</span>middle_index<span class="token punctuation">]</span><span class="token punctuation">:</span>
            start_index <span class="token operator">=</span> middle_index<span class="token operator">+</span><span class="token number">1</span>  <span class="token comment"># move goalpost</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            end_index <span class="token operator">=</span> middle_index<span class="token operator">-</span><span class="token number">1</span>  <span class="token comment"># move goalpost</span>

    <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>  <span class="token comment"># did not find the item</span></code></pre>
<p>This algorithm starts by considering the entire list (with the “goalposts” at either end. It then looks at the middle element. If that isn’t the target, then it moves the appropriate goalpost to that middle spot, thereby throwing away the half of the list and narrowing the search field. This continues until the target is found or the goalposts have moved “past” one another, at which point the search ends. See <a href="http://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html">this animation</a> for an example of how it works.</p>
<p>(Note that this is an example of <em>indefinite iteration</em>: you don’t know how many times you’ll need to cut the list in half before searching, so you use a <code>while</code> loop!)</p>
<p>So how fast is a binary search? Using a timer will demonstrate that <em>binary search</em> is much faster than <em>linear search</em> (as the list gets large), but how much faster?</p>
<p>The intuition behind the speed of a binary search is as follows: Each time through the loop (each “comparison”) effectively lets you reduce the size of the list by <em>half</em>. So if there are <strong><code>N</code></strong> items in the list, the first time through the loop reduces the list to <strong><code>N*(1/2)</code></strong> items, the second time through reduces is to <strong><code>N*(1/2)*(1/2)</code></strong>, etc. In the worst case, you will need to cut the list in half until you have reduced the list to exactly one item, or:</p>
<p>  <img src="img/searching/binary-search-eq1.png" title="Binary complexity equation" /></p>
<p>We can solve this equation for the number of <code>loops</code>:</p>
<p>  <img src="img/searching/binary-search-eq2.png" title="Binary complexity equation" /></p>
<p>Thus binary search’s speed is a <strong>logarithmic function</strong> of the size of the list: that is, if you double the size of the list, the number of comparisons you need to do (the number of times through the loop) <em>increases by just 1</em>.</p>
<div class="figure">
<img src="img/searching/logarithmic-time.png" alt="" />
<p class="caption">Logarithmic time complexity. Image by Nick Salloum.</p>
</div>
<p>This is <em>drastically</em> faster than a linear search…. however, it requires a list be sorted for it to work!</p>
</div>
<div id="slower-algorithms-sorting" class="section level3" number="7.4.3">
<h3><span class="header-section-number">7.4.3</span> Slower Algorithms: Sorting</h3>
<p>There are <a href="https://en.wikipedia.org/wiki/Sorting_algorithm">many, <em>many</em></a> different algorithms for sorting numbers, many of which have amusing names given to them by computer scientists (Python’s built-in <code>sorted()</code> method uses one called <a href="https://en.wikipedia.org/wiki/Timsort">Timsort</a>, named after the man who invented it). This chapter will discuss just one straightforward example for illustration purposes.</p>
<p>One such algorithm (<strong>Selection Sort</strong>) utilizes the “king-of-the-hill” search described above. This algorithm works as follows: search for (“select”) the smallest item in the list. Because it is the smallest, it must be the first item in the sorted list, and can be placed there. Next, select the second-smallest item in the list (the smallest of the “unsorted” items), and place that second in the “sorted” list. Continue with this process until the entire list is sorted!</p>
<pre class="language-python"><code><span class="token keyword">def</span> <span class="token function">selection_sort</span><span class="token punctuation">(</span>a_list<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token triple-quoted-string string">"""Sorts the list (in place)"""</span>

    <span class="token keyword">for</span> i <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span><span class="token builtin">len</span><span class="token punctuation">(</span>a_list<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>  <span class="token comment"># go through each spot in the list</span>
        <span class="token comment"># Do a "king-of-the-hill" search of the remaining items</span>
        selected_index <span class="token operator">=</span> i
        <span class="token keyword">for</span> j <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> <span class="token builtin">len</span><span class="token punctuation">(</span>a_list<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>a_list<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&lt;</span> a_list<span class="token punctuation">[</span>selected_index<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
                selected_index <span class="token operator">=</span> j

        <span class="token comment"># swap smallest into place (multi-assignment!)</span>
        a_list<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> a_list<span class="token punctuation">[</span>selected_index<span class="token punctuation">]</span> <span class="token operator">=</span> a_list<span class="token punctuation">[</span>selected_index<span class="token punctuation">]</span><span class="token punctuation">,</span> a_list<span class="token punctuation">[</span>i<span class="token punctuation">]</span></code></pre>
<p>To determine the speed of the <em>selection sort</em> algorithm, notice that the first time through the loop requires considering <strong><code>N</code></strong> different items (the whole loop). The second time requires checking <strong><code>N-1</code></strong> items, the third time <strong><code>N-2</code></strong> items, and so forth until the last time through the loop you only need to compare <code>2</code> then <code>1</code> items. These checks can then be summed into a series:</p>
<p>  <img src="img/searching/selection_sort_eq.png" title="Selection sort complexity equation" /></p>
<p>Selection sort’s speed is a <strong>quadratic function</strong> of the size of the list: that is, if you double the size of the list, the number of comparisons you need to do <em>quadruples!</em>.</p>
<p class="alert alert-info">
Faster sorting algorithms (like Python’s Timsort) get this speed down to “fast” <code>N*log2(N)</code> (“loglinear”), which is much better than <em>quadratic</em> algorithms but still notably slower than <em>linear</em> algorithms.
</p>
<p>For large lists, sorting a list is slower than just using a linear search on it… but once that list is sorted, you can use the ultra-fast binary search! This is a <strong>tradeoff</strong> that needs to be considered when trying to improve the efficiency of programs that work on large data sets: sometimes you need to spend some extra time up front to prepare (sort) the data, in order to be able to utilize (search) it more effectively.</p>
</div>
</div>
<div id="resources-6" class="section level2 unnumbered">
<h2>Resources</h2>
<div class="list-condensed">
<ul>
<li><a href="http://openbookproject.net/thinkcs/python/english3e/list_algorithms.html">List Algorithms (Downey)</a>, Sections 14.1 - 14.7</li>
<li><a href="http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html">What is Algorithm Analysis?</a> and <a href="http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html">Big-O Notation</a></li>
</ul>
</div>

</div>
</div>
            </section>

          </div>
        </div>
      </div>
<a href="dictionaries.html" class="navigation navigation-prev " aria-label="Previous page"><i class="fa fa-angle-left"></i></a>
<a href="functional-programming.html" class="navigation navigation-next " aria-label="Next page"><i class="fa fa-angle-right"></i></a>
    </div>
  </div>
<script src="libs/gitbook-2.6.7/js/app.min.js"></script>
<script src="libs/gitbook-2.6.7/js/clipboard.min.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-search.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-sharing.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-fontsettings.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-bookdown.js"></script>
<script src="libs/gitbook-2.6.7/js/jquery.highlight.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-clipboard.js"></script>
<script>
gitbook.require(["gitbook"], function(gitbook) {
gitbook.start({
"sharing": {
"github": true,
"facebook": false,
"twitter": false,
"linkedin": false,
"weibo": false,
"instapaper": false,
"vk": false,
"whatsapp": false,
"all": ["github", "facebook", "twitter", "google"],
"google": false
},
"fontsettings": {
"theme": "white",
"family": "sans",
"size": 2
},
"edit": {
"link": "https://github.com/infx511/book/edit/master/searching.Rmd",
"text": "Edit"
},
"history": {
"link": null,
"text": null
},
"view": {
"link": null,
"text": null
},
"download": null,
"search": {
"engine": "fuse",
"options": null
},
"toc": {
"collapse": "section",
"scroll_highlight": true
}
});
});
</script>

</body>

</html>