Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit149444b

Browse files
committed
Add Interpolation Search.
1 parent31344fa commit149444b

File tree

6 files changed

+119
-2
lines changed

6 files changed

+119
-2
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@ a set of rules that precisely define a sequence of operations.
8686
*`B`[Linear Search](src/algorithms/search/linear-search)
8787
*`B`[Jump Search](src/algorithms/search/jump-search) (or Block Search) - search in sorted array
8888
*`B`[Binary Search](src/algorithms/search/binary-search) - search in sorted array
89+
*`B`[Interpolation Search](src/algorithms/search/interpolation-search) - search in uniformly distributed sorted array
8990
***Sorting**
9091
*`B`[Bubble Sort](src/algorithms/sorting/bubble-sort)
9192
*`B`[Selection Sort](src/algorithms/sorting/selection-sort)
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
#Interpolation Search
2+
3+
**Interpolation search** is an algorithm for searching for a key in an array that
4+
has been ordered by numerical values assigned to the keys (key values).
5+
6+
For example we have a sorted array of`n` uniformly distributed values`arr[]`,
7+
and we need to write a function to search for a particular element`x` in the array.
8+
9+
**Linear Search** finds the element in`O(n)` time,**Jump Search** takes`O(√ n)` time
10+
and**Binary Search** take`O(Log n)` time.
11+
12+
The**Interpolation Search** is an improvement over Binary Search for instances,
13+
where the values in a sorted array are_uniformly_ distributed. Binary Search
14+
always goes to the middle element to check. On the other hand, interpolation
15+
search may go to different locations according to the value of the key being
16+
searched. For example, if the value of the key is closer to the last element,
17+
interpolation search is likely to start search toward the end side.
18+
19+
To find the position to be searched, it uses following formula:
20+
21+
```
22+
// The idea of formula is to return higher value of pos
23+
// when element to be searched is closer to arr[hi]. And
24+
// smaller value when closer to arr[lo]
25+
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))
26+
27+
arr[] - Array where elements need to be searched
28+
x - Element to be searched
29+
lo - Starting index in arr[]
30+
hi - Ending index in arr[]
31+
```
32+
33+
##Complexity
34+
35+
**Time complexity**:`O(log(log(n))`
36+
37+
##References
38+
39+
-[GeeksForGeeks](https://www.geeksforgeeks.org/interpolation-search/)
40+
-[Wikipedia](https://en.wikipedia.org/wiki/Interpolation_search)
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
importinterpolationSearchfrom'../interpolationSearch';
2+
3+
describe('interpolationSearch',()=>{
4+
it('should search elements in sorted array of numbers',()=>{
5+
expect(interpolationSearch([],1)).toBe(-1);
6+
expect(interpolationSearch([1],1)).toBe(0);
7+
expect(interpolationSearch([1],0)).toBe(-1);
8+
expect(interpolationSearch([1,1],1)).toBe(0);
9+
expect(interpolationSearch([1,2],1)).toBe(0);
10+
expect(interpolationSearch([1,2],2)).toBe(1);
11+
expect(interpolationSearch([10,20,30,40,50],40)).toBe(3);
12+
expect(interpolationSearch([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],14)).toBe(13);
13+
expect(interpolationSearch([1,6,7,8,12,13,14,19,21,23,24,24,24,300],24)).toBe(10);
14+
expect(interpolationSearch([1,2,3,700,800,1200,1300,1400,1900],600)).toBe(-1);
15+
expect(interpolationSearch([1,2,3,700,800,1200,1300,1400,1900],1)).toBe(0);
16+
expect(interpolationSearch([1,2,3,700,800,1200,1300,1400,1900],2)).toBe(1);
17+
expect(interpolationSearch([1,2,3,700,800,1200,1300,1400,1900],3)).toBe(2);
18+
expect(interpolationSearch([1,2,3,700,800,1200,1300,1400,1900],700)).toBe(3);
19+
expect(interpolationSearch([1,2,3,700,800,1200,1300,1400,1900],800)).toBe(4);
20+
expect(interpolationSearch([0,2,3,700,800,1200,1300,1400,1900],1200)).toBe(5);
21+
expect(interpolationSearch([1,2,3,700,800,1200,1300,1400,19000],800)).toBe(4);
22+
expect(interpolationSearch([0,10,11,12,13,14,15],10)).toBe(1);
23+
});
24+
});
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
/**
2+
* Interpolation search implementation.
3+
*
4+
*@param {*[]} sortedArray - sorted array with uniformly distributed values
5+
*@param {*} seekElement
6+
*@return {number}
7+
*/
8+
exportdefaultfunctioninterpolationSearch(sortedArray,seekElement){
9+
letleftIndex=0;
10+
letrightIndex=sortedArray.length-1;
11+
12+
while(leftIndex<=rightIndex){
13+
constrangeDelta=sortedArray[rightIndex]-sortedArray[leftIndex];
14+
constindexDelta=rightIndex-leftIndex;
15+
constvalueDelta=seekElement-sortedArray[leftIndex];
16+
17+
// If valueDelta is less then zero it means that there is no seek element
18+
// exists in array since the lowest element from the range is already higher
19+
// then seek element.
20+
if(valueDelta<0){
21+
return-1;
22+
}
23+
24+
// If range delta is zero then subarray contains all the same numbers
25+
// and thus there is nothing to search for unless this range is all
26+
// consists of seek number.
27+
if(!rangeDelta){
28+
// By doing this we're also avoiding division by zero while
29+
// calculating the middleIndex later.
30+
returnsortedArray[leftIndex]===seekElement ?leftIndex :-1;
31+
}
32+
33+
// Do interpolation of the middle index.
34+
constmiddleIndex=leftIndex+Math.floor(valueDelta*indexDelta/rangeDelta);
35+
36+
// If we've found the element just return its position.
37+
if(sortedArray[middleIndex]===seekElement){
38+
returnmiddleIndex;
39+
}
40+
41+
// Decide which half to choose for seeking next: left or right one.
42+
if(sortedArray[middleIndex]<seekElement){
43+
// Go to the right half of the array.
44+
leftIndex=middleIndex+1;
45+
}else{
46+
// Go to the left half of the array.
47+
rightIndex=middleIndex-1;
48+
}
49+
}
50+
51+
return-1;
52+
}

‎src/algorithms/search/jump-search/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,5 +23,5 @@ minimum when `m = √n`. Therefore, the best step size is `m = √n`.
2323

2424
##References
2525

26-
-[Wikipedia](https://en.wikipedia.org/wiki/Jump_search)
2726
-[GeeksForGeeks](https://www.geeksforgeeks.org/jump-search/)
27+
-[Wikipedia](https://en.wikipedia.org/wiki/Jump_search)

‎src/algorithms/search/jump-search/jumpSearch.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ import Comparator from '../../../utils/comparator/Comparator';
33
/**
44
* Jump (block) search implementation.
55
*
6-
*@param {*[]} sortedArray.
6+
*@param {*[]} sortedArray
77
*@param {*} seekElement
88
*@param {function(a, b)} [comparatorCallback]
99
*@return {number}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp