-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
211 lines (149 loc) · 10.4 KB
/
index.html
File metadata and controls
211 lines (149 loc) · 10.4 KB
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
<!DOCTYPE html>
<html class="no-js" xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Peter Stratton</title>
<link rel="canonical" href="http://peterstratton.com/">
<link href='http://fonts.googleapis.com/css?family=Alegreya:400italic,700italic,400,700' rel='stylesheet' type='text/css'>
<script type="text/javascript" async
src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=MML_CHTML">
</script>
<link href="css/foundation.min.css" rel="stylesheet" type="text/css" />
<link href="css/foundation-icons/foundation-icons.css" rel="stylesheet" type="text/css" />
<link href="js/vendor/highlight/styles/tomorrow-night.css" rel="stylesheet" type="text/css" />
<link href="css/app.css" rel="stylesheet" type="text/css" />
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-9050798-1', 'auto');
ga('send', 'pageview');
</script>
</head>
<body>
<!-- Start Top Bar -->
<div class="top-bar">
<div class="top-bar-left">
<ul class="menu">
<li class="menu-text">Peter Stratton</li>
</ul>
</div>
<div class="top-bar-right">
<ul class="menu">
<li class="active" ><a href="/">Home</a></li>
<li ><a href="/archives/">Archives</a></li>
<li >
<a href="/pages-output/about/">About</a>
</li>
<li><a href="/feed.xml">RSS</a></li>
</ul>
</div>
</div>
<!-- End Top Bar -->
<!-- Primary Callout -->
<div class="callout large primary banner">
<div class="row column text-center">
<h3 class="bannertext">When do I see a photograph, when a reflection?</h3>
</div>
</div>
<!-- End Primary Callout -->
<!-- Content -->
<div class="row" id="content">
<div class="medium-8 columns">
<div>
<div id="post">
<div class="blog-post">
<h3>The Linear Search Algorithm <small>2/9/17</small></h3>
</div>
<div>
<hr/><h4><a name="<strong>introduction</strong>"></a><strong>Introduction</strong></h4><p>Self-taught developers tend to have a very pragmatic approach to software development. We learnt from projects, tutorials, practical courses, and technical books. There's nothing wrong with that. But, we're missing some of the fundamentals that traditional Computer Science majors get during their coursework. The goal of this series is to expose self-taught developers to algorithm design and anaylsis. This post covers Linear Search, one of the most commonly used algorithms in computer science.</p><h4><a name="<strong>linear_search_-_<code>o(n)_complexity</code></strong>"></a><strong>Linear Search - <code>O(n) Complexity</code></strong></h4><p>Search functions find the position of an item in a list. Linear Search is the simplest form of search. It simply starts at the beginning and examines every item until it finds a match. The worst case scenario would be when the item being searched for is at the very end of the list. Here's a visual representation of linear search across a 15 element sequence where we're looking for the value 9:</p><p><img src="/img/LinearSearch/LinearSearch.png" alt="Linear Search" /></p><p>A home-grown linear search implementation in Python might look something like this:</p><pre><code class="python">my_list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
def linear_search(target, src_list):
for i in range(0, len(src_list)):
if src_list[i] == target:
return i
raise ValueError
linear_search(9, my_list) # 8
linear_search(1, my_list) # 0
linear_search(42, my_list) # ValueError
</code></pre><p>However, as I've mentioned previously, most programming languages ship with common algorithms already built in. In Python, the Sequence Types implement the <code>index()</code> method, which performs a linear search similar to our homegrown solution.</p><pre><code class="python">my_list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
my_list.index(9) # 8
my_list.index(1) # 0
my_list.index(42) # ValueError
# since strings Sequence Types, we can call index on them as well
'foobarbaz'.index('r') # 5
# it's worth remembering that linear search returns the position of the first element it matches on
'foobarbaz'.index('b') # 3
</code></pre><h4><a name="<strong>summary</strong>"></a><strong>Summary</strong></h4><table><thead><tr><th>Pros</th><th>Cons</th></tr></thead><tbody><tr><td>super simple to implement</td><td>slower than most other forms of search</td></tr><tr><td>fairly performant</td><td>scales linearly</td></tr><tr><td>works on unsorted lists</td><td></td></tr><tr><td>memory efficient (doesn't require copying)</td><td></td></tr></tbody></table><h4><a name="<strong>conclusion</strong>"></a><strong>Conclusion</strong></h4><p>The fact that linear search works on unsorted lists is probably its most compelling feature. You'll use it all the time, and it's a great example of O(n) algorithmic complexity. Just remember, any time you have to look at every item in a sequence once (and only once), it's O(n).<br /></p><p>As usual, feel free to hit me up on <a href='https://twitter.com/halescode'>Twitter</a> or send me a message on <a href='https://www.linkedin.com/in/peterstratton'>LinkedIn</a> if you have any questions!</p>
</div>
<div class="callout">
<ul class="menu simple">
<li><b>Tags: </b></li>
<li><a href="/tags-output/impostors guide/">impostors guide</a></li>
<li><a href="/tags-output/algorithms/">algorithms</a></li>
<li><a href="/tags-output/computer science/">computer science</a></li>
</ul>
</div>
<div id="prev-next">
<a class="right" href="/posts-output/2017-01-28-postgres-and-clojure-using-clojure-java-jdbc/">Postgres and Clojure Using clojure.java.jdbc »</a>
</div>
</div>
</div>
</div>
<!-- Side Bar -->
<div class="medium-3 columns" data-sticky-container>
<div class="sticky" data-sticky data-anchor="content">
<h4>Recent Posts</h4>
<ul>
<li><a href="/posts-output/2017-02-09-linear-search/">The Linear Search Algorithm</a></li>
<li><a href="/posts-output/2017-01-28-postgres-and-clojure-using-clojure-java-jdbc/">Postgres and Clojure Using clojure.java.jdbc</a></li>
<li><a href="/posts-output/2017-01-04-algorithms-logarithms-and-big-o/">Algorithms, Logarithms, and Big O</a></li>
<li><a href="/posts-output/2016-12-13-imposters-guide-to-software-development/">The Impostors Guide to Software Development</a></li>
<li><a href="/posts-output/2016-11-10-hello-world/">Test post, please ignore.</a></li>
</ul>
<h4>Tags</h4>
<ul>
<li><a href="/tags-output/impostors guide/">impostors guide</a></li>
<li><a href="/tags-output/algorithms/">algorithms</a></li>
<li><a href="/tags-output/computer science/">computer science</a></li>
<li><a href="/tags-output/ClojureVids/">ClojureVids</a></li>
<li><a href="/tags-output/Clojure/">Clojure</a></li>
<li><a href="/tags-output/Postgres/">Postgres</a></li>
</ul>
<h4>Video</h4>
<ul id="sidebar-links">
<li><a href="http://clojurevids.com"><img class="sidebar-link" src="/img/sidebar_icons/clojurevids.png" alt="ClojureVids"></a></li>
<li><a href="https://www.youtube.com/channel/UCrwwOZ4h2FQhAdTMfjyQfQA"><img class="sidebar-link" src="/img/sidebar_icons/youtube.png" alt="YouTube"></a></li>
</ul>
<h4>Social</h4>
<ul id="sidebar-links">
<li><a href="https://www.linkedin.com/in/peterstratton"><img class="sidebar-link" src="/img/sidebar_icons/linkedin.png" alt="LinkedIn"</a></li>
<li><a href="https://twitter.com/clojurevids"><img class="sidebar-link" src="/img/sidebar_icons/twitter.png" alt="Twitter"</a></li>
</ul>
</div>
</div> <!-- End Side Bar -->
</div>
<!-- End Content -->
<!-- Footer -->
<footer class="row">
<div class="large-12 columns">
<hr />
<div class="row">
<div class="large-6 columns">
<p>Copyright © 2017 Peter Stratton</p>
</div>
<div class="large-6 columns">
<p style="text-align: right;">Powered by <a href="http://cryogenweb.org">Cryogen</a></p>
</div>
</div>
</div>
</footer>
<!-- End Footer -->
<script src="https://code.jquery.com/jquery-2.1.4.min.js"></script>
<script src="js/vendor/foundation.min.js" type="text/javascript"></script>
<script src="js/app.js" type="text/javascript"></script>
<script src="js/vendor/highlight/highlight.pack.js" type="text/javascript"></script>
<script>hljs.initHighlightingOnLoad();</script>
</body>
</html>