FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaScript/Search/BinarySearch.js at master · TheAlgorithms/JavaScript · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
TheAlgorithms
/
JavaScript
Public
Uh oh!
There was an error while loading.
Please reload this page
.
Notifications
You must be signed in to change notification settings
Fork
5.8k
Star
34.2k
Code
Issues
21
Pull requests
192
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaScript
/
Search
/
BinarySearch.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
52 lines (46 loc) · 1.71 KB
Breadcrumbs
JavaScript
/
Search
/
BinarySearch.js
Copy path
File metadata and controls
52 lines (46 loc) · 1.71 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
/* Binary Search: https://en.wikipedia.org/wiki/Binary_search_algorithm
*
* Search a sorted array by repeatedly dividing the search interval
* in half. Begin with an interval covering the whole array. If the value of the
* search key is less than the item in the middle of the interval, narrow the interval
* to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the
* value is found or the interval is empty.
*/
function
binarySearchRecursive
(
arr
,
x
,
low
=
0
,
high
=
arr
.
length
-
1
)
{
const
mid
=
Math
.
floor
(
low
+
(
high
-
low
)
/
2
)
if
(
high
>=
low
)
{
if
(
arr
[
mid
]
===
x
)
{
// item found => return its index
return
mid
}
if
(
x
<
arr
[
mid
]
)
{
// arr[mid] is an upper bound for x, so if x is in arr => low <= x < mid
return
binarySearchRecursive
(
arr
,
x
,
low
,
mid
-
1
)
}
else
{
// arr[mid] is a lower bound for x, so if x is in arr => mid < x <= high
return
binarySearchRecursive
(
arr
,
x
,
mid
+
1
,
high
)
}
}
else
{
// if low > high => we have searched the whole array without finding the item
return
-
1
}
}
function
binarySearchIterative
(
arr
,
x
,
low
=
0
,
high
=
arr
.
length
-
1
)
{
while
(
high
>=
low
)
{
const
mid
=
Math
.
floor
(
low
+
(
high
-
low
)
/
2
)
if
(
arr
[
mid
]
===
x
)
{
// item found => return its index
return
mid
}
if
(
x
<
arr
[
mid
]
)
{
// arr[mid] is an upper bound for x, so if x is in arr => low <= x < mid
high
=
mid
-
1
}
else
{
// arr[mid] is a lower bound for x, so if x is in arr => mid < x <= high
low
=
mid
+
1
}
}
// if low > high => we have searched the whole array without finding the item
return
-
1
}
export
{
binarySearchIterative
,
binarySearchRecursive
}
Back
|
FazBrowse Home
|
New Git URL