Skip to content

Commit a47923d

Browse files
LefterisDLefterisD
committed
Fixed exponentialSearch.js and interpolationSearch.js
1 parent 6dbb849 commit a47923d

File tree

2 files changed

+74
-80
lines changed

2 files changed

+74
-80
lines changed

‎Search/ExponentialSearch.js

Lines changed: 42 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,61 +1,58 @@
1-
/*
1+
/**
22
* Exponential Search
33
*
4-
* The algorithm consists of two stages. The first stage determines a
5-
* range in which the search key would reside if it were in the list.
4+
* The algorithm consists of two stages. The first stage determines a
5+
* range in which the search key would reside if it were in the list.
66
* In the second stage, a binary search is performed on this range.
7-
*
87
*
9-
*
8+
*
9+
*
1010
*/
1111

12-
function binarySearch(arr, x, floor, ceiling) {
13-
// Middle index
14-
let mid = Math.floor((floor + ceiling) / 2);
15-
16-
// If value is at the mid position return this position
17-
if (arr[mid] === x) {
18-
return mid;
19-
}
20-
21-
if(floor > ceiling) return -1;
22-
23-
// If the middle element is great than the value
24-
// search the left part of the array
25-
if (arr[mid] > value) {
26-
return binarySearch(arr, value, floor, mid - 1);
27-
//If the middle element is lower than the value
28-
//search the right part of the array
29-
} else {
30-
return binarySearch(arr, value, mid + 1, ceiling);
31-
}
32-
33-
12+
function binarySearch (arr, x, floor, ceiling) {
13+
// Middle index
14+
const mid = Math.floor((floor + ceiling) / 2)
15+
16+
// If value is at the mid position return this position
17+
if (arr[mid] === x) {
18+
return mid
19+
}
20+
21+
if (floor > ceiling) return -1
22+
23+
// If the middle element is great than the value
24+
// search the left part of the array
25+
if (arr[mid] > value) {
26+
return binarySearch(arr, value, floor, mid - 1)
27+
// If the middle element is lower than the value
28+
// search the right part of the array
29+
} else {
30+
return binarySearch(arr, value, mid + 1, ceiling)
31+
}
3432
}
3533

34+
function exponentialSearch (arr, length, value) {
35+
// If value is the first element of the array return this position
36+
if (arr[0] === value) {
37+
return 0
38+
}
3639

37-
function exponentialSearch(arr, length, value) {
38-
// If value is the first element of the array return this position
39-
if (arr[0] == value) {
40-
return 0;
41-
}
42-
43-
// Find range for binary search
44-
let i = 1;
45-
while (i < length && arr[i] <= value) {
46-
i = i * 2;
47-
}
40+
// Find range for binary search
41+
let i = 1
42+
while (i < length && arr[i] <= value) {
43+
i = i * 2
44+
}
4845

49-
// Call binary search for the range found above
50-
return binarySearch(arr, value, i / 2, Math.min(i, length));
46+
// Call binary search for the range found above
47+
return binarySearch(arr, value, i / 2, Math.min(i, length))
5148
}
5249

53-
let arr = [2, 3, 4, 10, 40, 65 , 78 , 100];
54-
let value = 78;
55-
let result = exponentialSearch(arr, arr.length, value);
50+
const arr = [2, 3, 4, 10, 40, 65, 78, 100]
51+
const value = 78
52+
const result = exponentialSearch(arr, arr.length, value)
5653

5754
if (result < 0) {
58-
console.log("Element not found");
55+
console.log('Element not found')
5956
} else {
60-
console.log("Element found at position :" + result);
57+
console.log('Element found at position :' + result)
6158
}

‎Search/InterpolationSearch.js

Lines changed: 32 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -1,49 +1,46 @@
1-
/*
1+
/**
22
* Interpolation Search
3-
*
3+
*
44
* Time Complexity:
55
* -Best case: O(1)
66
* -Worst case: O(n)
77
* -O((log(log(n))) If the data are uniformly distributed
88
*
9-
*
9+
*
1010
*/
1111

12-
function interpolationSearch(arr, key) {
13-
14-
let length = arr.length - 1;
15-
let low = 0;
16-
let high = length;
17-
let position = -1;
18-
let delta = -1;
19-
20-
//Because the array is sorted the key must be between low and high
21-
while (low <= high && key >= arr[low] && key <= arr[high]) {
22-
23-
delta = (key - arr[low]) / (arr[high] - arr[low]);
24-
position = low + Math.floor((high - low) * delta);
25-
26-
//Target found return its position
27-
if (arr[position] === key) {
28-
return position;
29-
}
12+
function interpolationSearch (arr, key) {
13+
const length = arr.length - 1
14+
let low = 0
15+
let high = length
16+
let position = -1
17+
let delta = -1
18+
19+
// Because the array is sorted the key must be between low and high
20+
while (low <= high && key >= arr[low] && key <= arr[high]) {
21+
delta = (key - arr[low]) / (arr[high] - arr[low])
22+
position = low + Math.floor((high - low) * delta)
23+
24+
// Target found return its position
25+
if (arr[position] === key) {
26+
return position
27+
}
3028

31-
//If the key is larger then it is in the upper part of the array
32-
if (arr[position] < key) {
33-
low = position + 1;
34-
//If the key is smaller then it is in the lower part of the array
35-
} else {
36-
high = position - 1;
37-
}
29+
// If the key is larger then it is in the upper part of the array
30+
if (arr[position] < key) {
31+
low = position + 1
32+
// If the key is smaller then it is in the lower part of the array
33+
} else {
34+
high = position - 1
3835
}
36+
}
3937

40-
return -1;
38+
return -1
4139
}
4240

41+
const arr = [2, 6, 8, 10, 12, 14, 16, 18, 20, 22, 26, 34, 39]
4342

44-
let arr = [2, 6, 8, 10, 12, 14, 16, 18, 20, 22, 26, 34, 39];
45-
46-
console.log("Found at position :" + interpolationSearch(arr, 2));
47-
console.log("Found at position :" + interpolationSearch(arr, 12));
48-
console.log("Found at position :" + interpolationSearch(arr, 1000));
49-
console.log("Found at position :" + interpolationSearch(arr, 39));
43+
console.log('Found at position :' + interpolationSearch(arr, 2))
44+
console.log('Found at position :' + interpolationSearch(arr, 12))
45+
console.log('Found at position :' + interpolationSearch(arr, 1000))
46+
console.log('Found at position :' + interpolationSearch(arr, 39))

0 commit comments

Comments
 (0)