FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaScript/Search/TernarySearch.js at patch-1 · MMABSOUT/JavaScript · GitHub
MMABSOUT
/
JavaScript
Public
forked from
TheAlgorithms/JavaScript
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaScript
/
Search
/
TernarySearch.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
86 lines (79 loc) · 2.85 KB
Breadcrumbs
JavaScript
/
Search
/
TernarySearch.js
Copy path
File metadata and controls
86 lines (79 loc) · 2.85 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
/* Ternary search is similar to binary search but it divides the sorted array
* into three parts and determines which part the key lies in. The array will
* be divided into three intervals by using two middle points, mid1 and mid2.
* The value of the key will first be compared with the two mid points, the value
* will be returned if there is a match. Then, if the value of the key is less
* than mid1, narrow the interval to the first part. Else, if the value of the
* key is greater than mid2, narrow the interval to the third part. Otherwise,
* narrow the interval to the middle part. Repeat the steps until the value is
* found or the interval is empty (value not found after checking all elements).
*
* Reference: https://www.geeksforgeeks.org/ternary-search/
*/
function
ternarySearchRecursive
(
arr
,
key
,
low
=
0
,
high
=
arr
.
length
-
1
)
{
if
(
high
>=
low
)
{
// find the mid1 and mid2
const
mid1
=
Math
.
floor
(
low
+
(
high
-
low
)
/
3
)
const
mid2
=
Math
.
floor
(
high
-
(
high
-
low
)
/
3
)
// check if key is found at any mid
if
(
arr
[
mid1
]
===
key
)
{
// return index of key if found
return
mid1
}
if
(
arr
[
mid2
]
===
key
)
{
// return index of key if found
return
mid2
}
// since the key is not found at mid,
// check in which region it is present
// and repeat the Search operation
// in that region
if
(
key
<
arr
[
mid1
]
)
{
// the key lies in between low and mid1
return
ternarySearchRecursive
(
arr
,
key
,
low
,
mid1
-
1
)
}
else
if
(
key
>
arr
[
mid2
]
)
{
// the key lies in between mid2 and high
return
ternarySearchRecursive
(
arr
,
key
,
mid2
+
1
,
high
)
}
else
{
// the key lies in between mid1 and mid2
return
ternarySearchRecursive
(
arr
,
key
,
mid1
+
1
,
mid2
-
1
)
}
}
else
{
// if low > high => we have searched the whole array without finding the item
return
-
1
}
}
function
ternarySearchIterative
(
arr
,
key
,
low
=
0
,
high
=
arr
.
length
-
1
)
{
while
(
high
>=
low
)
{
// find the mid1 and mid2
const
mid1
=
Math
.
floor
(
low
+
(
high
-
low
)
/
3
)
const
mid2
=
Math
.
floor
(
high
-
(
high
-
low
)
/
3
)
// check if key is found at any mid
if
(
arr
[
mid1
]
===
key
)
{
// return index of key if found
return
mid1
}
if
(
arr
[
mid2
]
===
key
)
{
// return index of key if found
return
mid2
}
// since the key is not found at mid,
// check in which region it is present
// and repeat the Search operation
// in that region
if
(
key
<
arr
[
mid1
]
)
{
// the key lies in between low and mid1
high
=
mid1
-
1
}
else
if
(
key
>
arr
[
mid2
]
)
{
// the key lies in between mid2 and high
low
=
mid2
+
1
}
else
{
// the key lies in between mid1 and mid2
low
=
mid1
+
1
high
=
mid2
-
1
}
}
// the key was not found
return
-
1
}
export
{
ternarySearchRecursive
,
ternarySearchIterative
}
Back
|
FazBrowse Home
|
New Git URL