-
Notifications
You must be signed in to change notification settings - Fork 731
/
search.html
232 lines (205 loc) · 8.97 KB
/
search.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="description" content="">
<meta name="that js dude" content="">
<title>JS: interview Questions -5</title>
<link rel="shortcut icon" href="images/favicon.jpg">
<link rel="stylesheet" href="css/bootstrap.min.css" >
<link rel="stylesheet" href="css/zenburn.css">
<!-- Custom styles for this template -->
<style>
/* Move down content because we have a fixed navbar that is 50px tall */
body {
padding-bottom: 20px;
}
.purpleBold{
color:purple;
font-weight: bold;
}
.gray{
color: gray;
}
.blueish{
color: rgba(151, 182, 209, 0.98);
}
.singInStuff{
margin-top: 9px;
}
#uName{
margin-top: -7px;
}
.skipListItem{
list-style-type: none;
}
.skipListItem a{
color: inherit;
}
a:visited
{
color: rgba(218, 209, 149, 0.98);
}
.padding10Px{
padding: 10px;
}
/*style for demo*/
</style>
<!-- Just for debugging purposes. Don't actually copy this line! -->
<!--[if lt IE 9]><script src="docs-assets/js/ie8-responsive-file-warning.js"></script><![endif]-->
<!-- HTML5 shim and Respond.js IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
<script src="https://oss.maxcdn.com/libs/respond.js/1.3.0/respond.min.js"></script>
<![endif]-->
</head>
<body>
<!-- Main jumbotron for a primary marketing message or call to action -->
<div class="jumbotron">
<div class="container">
<h1>JS: Interview Questions</h1>
<h4>Search and sort related interview questions for intermediate JavaScript developers</h4>
<h2>part-5: intermediate</h2>
<p>June 29, 2014</p>
<!-- <div id="fb-root"></div><div class="fb-like" data-href="http://www.thatjsdude.com/interview/dom.html" data-layout="button_count" data-action="like" data-show-faces="false" data-share="false"></div><div class="g-plusone"></div>
--> </div>
</div>
<div class="container container-fluid">
<!-- Example row of columns -->
<div class="row center">
<!-- <iframe width="853" height="480" src="//www.youtube.com/embed/Rx_JFOSxgpY" frameborder="0" allowfullscreen></iframe> -->
</div>
<!-- <p class="gray">if you are little more comfortable or claim to be comfortable with javascript, these questions would not be enough for you. more coming</p>
<p class="gray"> <span class="purpleBold">More Questions</span> <a href="css.html">css interview questions</a>, <a href="html.html">html interview questions</a> </p> -->
<div id="questionList">
<h2>todo list</h2>
<ol>
<li>add questions</li>
<li></li>
<li></li>
<li></li>
<li></li>
</ol>
</div>
<div id="binarySearch">
<h2>binary search</h2>
<p><strong>Question:</strong> How to implement binary search algorithm?</p>
<p><strong>Answer:</strong>Binary search tries to find an item in a sorted list. For example, if you have an array like <code>[3,9,11,21,32,37,43,56,63,69,78]</code> and you are looking for 69.</p>
<p><strong>How it works:</strong>Lets select the middle one, you got: 37. You are looking for 69. As you know, the array is sorted, you will know that 69 will be after 37. This means upper half of the array. Now, you will go and check the middle item of the upper half of the array. In that way, you are saving time to search the item in the lower half of the array.</p>
<p>The middle item of the upper half of the array is 63. Which is smaller than the number you are looking for. Hence, you can skip the lower part of the upper half. This means, your item will be in the top most quarter of the array. Now, you will keep the right side and pick the middle</p>
<p>The middle of the right side is 69. Thats what you were looking for.</p>
<p><strong>Why binary search</strong> If you were using linear search (start from the left and check one by one), you have to check 10 times to find the item. If you use binary search, you get after three times. You see the benefits!!</p>
<img src="images/binarySearch.png" alt="">
<p>Now if you have a million items in an array. For example, you have number 0 to 1000,000 and you want to find out 696,969. The binary search will take only 17 steps to find the item. where as if you start a linear search, it will take 696,969 steps to find the item.</p>
<pre><code>
function binarySearchIterative(arr, val){
var start = 0,
end = arr.length-1,
mid,
midVal;
while(end >= start){
mid = Math.floor((start+end)/2);
midVal = arr[mid];
if(midVal==val)
return mid;
if(val<midVal)
end = mid - 1;
if(val>midVal)
start = mid + 1;
}
return -1;
}
//try it now
binarySearchIterative([1,2,3,4,5], 1); //0
binarySearchIterative([1,2,3,4,5], 5); //4
binarySearchIterative([1,2,3,4,5], 55); //-1
</code></pre>
<p><strong>Complexity</strong></p>
<pstrong Performance</p>
<p>Recusrive algo</p>
<pre><code>
function binarySearchRecursive(arr, val, startIdx, endIdx){
var mid = Math.floor((startIdx + endIdx)/2),
midVal = arr[mid];
if(midVal == val)
return mid;
if (endIdx < startIdx)
return -1;
if (val<midVal)
return binarySearchRecursive(arr, val, startIdx, mid -1);
else if (val > midVal)
return binarySearchRecursive(arr, val, mid + 1, endIdx);
}
//try it now
binarySearchRecursive([1,2,3,4,5], 1, 0, 4); //0
binarySearchRecursive([1,2,3,4,5], 5, 0, 4); //4
binarySearchRecursive([1,2,3,4,5], 2, 0, 4); //1
binarySearchRecursive([1,2,3,4,5], 22, 0, 4); //-1
</code></pre>
<p>ref: <a href="http://en.wikipedia.org/wiki/Binary_search_algorithm">binary search</a></p>
</div>
<div>
<h3 class="purpleBold">Express anger!</h3>
<!-- <p class="gray">Feel free to express your anger (sorry folks, you have to use g+.). Also point out my mistakes ( technical, wrong answer, spelling, grammar, sentence..., whatever), let your dude learn and grow.</p>
<script src="https://apis.google.com/js/plusone.js"></script>
<div class="g-comments"
data-href="http://www.thatjsdude.com/interview/dom.html"
data-width="642"
data-first_party_property="BLOGGER"
data-view_type="FILTERED_POSTMOD">
</div> -->
</div>
<hr>
<footer>
<p>©thatJSDude 2014</p>
</footer>
</div> <!-- /container -->
<!-- Bootstrap core JavaScript
================================================== -->
<!-- Placed at the end of the document so the pages load faster -->
<script src="js/jquery-2.0.3.min.js"></script>
<script src="js/bootstrap.min.js"></script>
<script src="js/highlight.pack.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
<script src="js/toggleExample.js"></script>
<script type="text/javascript">
// //social plugins
// //g+
// (function() {
// var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true;
// po.src = 'https://apis.google.com/js/platform.js';
// var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s);
// })();
// //fb
// (function(d, s, id) {
// var js, fjs = d.getElementsByTagName(s)[0];
// if (d.getElementById(id)) return;
// js = d.createElement(s); js.id = id;
// js.src = "//connect.facebook.net/en_US/all.js#xfbml=1";
// fjs.parentNode.insertBefore(js, fjs);
// }(document, 'script', 'facebook-jssdk'));
</script>
<script type="text/javascript">
document.getElementById('listToDestroy').addEventListener('click', function (e) {
var elm = e.target.parentNode;
elm.parentNode.removeChild(elm);
e.preventDefault();
});
document.getElementById('doubleHolder').addEventListener('click', function (e) {
if(e.target.classList.contains('double')){
var btn = document.createElement('button');
btn.setAttribute('class', 'double');
btn.innerHTML = 'double';
var btn2 = document.createElement('button');
btn2.setAttribute('class', 'double');
btn2.innerHTML = 'double';
this.appendChild(btn);
this.appendChild(btn2);
this.removeChild(e.target);
}
});
</script>
</body>
</html>