-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinarySearch.html
More file actions
144 lines (138 loc) · 5.15 KB
/
binarySearch.html
File metadata and controls
144 lines (138 loc) · 5.15 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
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Binary Search</title>
<!-- Importing Mathjax -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.4/latest.js?config=AM_CHTML"></script>
<!-- Bootstrap css -->
<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.5.2/css/bootstrap.min.css"
integrity="sha384-JcKb8q3iqJ61gNV9KGb8thSsNjpSL0n8PARn9HuZOnIxN0hoP+VmmDGMN5t9UJ0Z" crossorigin="anonymous" />
<!-- Google Fonts -->
<link
href="https://fonts.googleapis.com/css2?family=Dancing+Script:wght@700&family=Roboto+Mono:ital@1&family=Roboto+Slab&family=Roboto:wght@400;700&display=swap"
rel="stylesheet" />
<!-- JASV CSS -->
<link rel="stylesheet" href="css/JSAV.css" />
<!-- General CSS -->
<link rel="stylesheet" href="css/style.css" />
</head>
<body>
<!-- Navigation -->
<div class="sidenav sticky">
<h5 id="Home"><a class="nav-link" href="index.html">Home</a></h5>
<div id="accordion">
<div class="card">
<div class="card-header" id="headingOne">
<h5 class="mb-auto">
<button class="btn btn-link" data-toggle="collapse" data-target="#collapseOne"
aria-expanded="true" aria-controls="collapseOne">
Searching
</button>
</h5>
</div>
<div id="collapseOne" class="collapse show" aria-labelledby="headingOne" data-parent="#accordion">
<div class="card-body">
<ul class="navbar-nav mr-auto">
<li class="nav-item active">
<a class="nav-link" href="#">Binary Search<span class="sr-only">(current)</span></a>
</li>
</ul>
</div>
</div>
</div>
<div class="card">
<div class="card-header" id="headingTwo">
<h5 class="mb-0">
<button class="btn btn-link collapsed" data-toggle="collapse" data-target="#collapseTwo"
aria-expanded="false" aria-controls="collapseTwo">
Sorting
</button>
</h5>
</div>
<div id="collapseTwo" class="collapse" aria-labelledby="headingTwo" data-parent="#accordion">
<div class="card-body">
<ul class="navbar-nav mr-auto">
<li class="nav-item">
<a class="nav-link" href="bubbleSort.html">Bubble Sort</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<!-- Visulization -->
<div class="content">
<div id="container">
<h1>Binary Search</h1>
<p>Enter the number you want to search for</p>
<div class="col-6 col-lg-3 input-group mb-3">
<input type="text" id="requiredNumber" class="form-control" placeholder="Number in the array" />
<div class="input-group-append">
<button class="btn btn-outline-secondary startButton" type="button">Start
<img src="images/play-button.png" class="start" alt="play-button" />
</button>
</div>
</div>
<p class="jsavoutput jsavline"></p>
<div class="jsavcanvas"></div>
<div class="jsavcontrols"></div>
</div>
<div class="explanation row">
<div class="code col-md-6 col-12">
<h4>Algorithm</h4>
<p>
binarySearch(x,arr,left,right)<br>
middle = (left + right)/2 <br>
if(left > right) <br>
return -1 <br>
else if(arr[middle]
< x) <br>
return binarySearch(x,arr,middle+1,right) <br>
else if(arr[middle] > x) <br>
return binarySearch(x,arr,left,middle-1) <br>
else <br>
return middle <br>
</p>
</div>
<div class="analysis col-md-6 col-12">
<h4>Analysis</h4>
<p>The equation for the recursive algorithm is: `T(n)=T(n/2)+C` <br>
at each recursive call the array size is divided in half and the work done outside the recursion
call
is constant which is calculating the middle index.<br>
using master theorm where: `a=1,b=2` <br>
Then: `f(n)=1`<br>
`n^(log_b a)=n^(log_2 1)=1` <br>
which means the complexity of the algorthim is <br>
`Theta(logn)`
</p>
</div>
</div>
</div>
<!-- Importing Jquery -->
<script src="js/jquery.min.js"></script>
<!-- Importing Popper -->
<script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.1/dist/umd/popper.min.js"
integrity="sha384-9/reFTGAW83EW2RDu2S0VKaIzap3H66lZH81PoYlFhbGU+6BZp6G7niu735Sk7lN" crossorigin="anonymous">
</script>
<!-- Importing Bootstrap -->
<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.5.2/js/bootstrap.min.js"
integrity="sha384-B4gt1jrGC7Jh4AgTPSdUtOBvfO8shuf57BaghqFfPlYxofvL8/KUEfYiJOMMV+rV" crossorigin="anonymous">
</script>
<!-- Importing Jquery-UI -->
<script src="js/jquery-ui.min.js"></script>
<!-- Importing Jquery-transit -->
<script src="js/jquery.transit.js"></script>
<!-- Importing Raphael -->
<script src="js/raphael.js"></script>
<!-- Importing JSAV Library -->
<script src="js/JSAV.js"></script>
<!-- Importing Private JS -->
<script src="js/index.js"></script>
<!-- Importing Binary-Search -->
<script src="js/binarySearch.js"></script>
</body>
</html>