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

Commit888ad51

Browse files
duffman85mgechev
andauthored
Add interpolation algo (mgechev#158)
* Add interpolation algo* Update src/searching/interpolation-search.jsCo-authored-by: Minko Gechev <mgechev@gmail.com>
1 parentfc29658 commit888ad51

File tree

2 files changed

+76
-0
lines changed

2 files changed

+76
-0
lines changed

‎src/searching/interpolation-search.js

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
(function(exports){
2+
'use strict';
3+
/**
4+
* Searches for specific element in a given array using
5+
* the jump search algorithm.<br><br>
6+
* Time complexity: O(log N).
7+
*
8+
*@example
9+
*
10+
* var search = require('path-to-algorithms/src/searching/'+
11+
* 'interpolation-search').interpolationSearch;
12+
* console.log(search([1, 2, 3, 4, 5], 4)); // 3
13+
*
14+
*@public
15+
*@module searching/interpolation-search
16+
*@param {Array} sortedArray Input array.
17+
*@param {Number} seekIndex of the element which index should be found.
18+
*@returns {Number} Index of the element or -1 if not found.
19+
*/
20+
functioninterpolationSearch(sortedArray,seekIndex){
21+
letleftIndex=0;
22+
letrightIndex=sortedArray.length-1;
23+
24+
while(leftIndex<=rightIndex){
25+
constrangeDiff=sortedArray[rightIndex]-sortedArray[leftIndex];
26+
constindexDiff=rightIndex-leftIndex;
27+
constvalueDiff=seekIndex-sortedArray[leftIndex];
28+
29+
if(valueDiff<0){
30+
return-1;
31+
}
32+
33+
if(!rangeDiff){
34+
returnsortedArray[leftIndex]===seekIndex ?leftIndex :-1;
35+
}
36+
37+
constmiddleIndex=
38+
leftIndex+Math.floor((valueDiff*indexDiff)/rangeDiff);
39+
40+
if(sortedArray[middleIndex]===seekIndex){
41+
returnmiddleIndex;
42+
}
43+
44+
if(sortedArray[middleIndex]<seekIndex){
45+
leftIndex=middleIndex+1;
46+
}else{
47+
rightIndex=middleIndex-1;
48+
}
49+
}
50+
51+
return-1;
52+
}
53+
exports.interpolationSearch=interpolationSearch;
54+
})(typeofwindow==='undefined' ?module.exports :window);
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
varinterpolationSearch=require('../../src/searching/interpolation-search')
2+
.interpolationSearch;
3+
4+
describe('Interpolation search',function(){
5+
'use strict';
6+
7+
it('should find the element at position 0 ',function(){
8+
expect(interpolationSearch([1,2,3,4,6,8],1)).toBe(0);
9+
});
10+
11+
it('should find the element at position 4 ',function(){
12+
expect(interpolationSearch([1,2,3,4,6,8],6)).toBe(4);
13+
});
14+
15+
it('should return -1 if element is not found',function(){
16+
expect(interpolationSearch([1,2,3,4,6,8],17)).toBe(-1);
17+
});
18+
19+
it('should return -1 if array is empty',function(){
20+
expect(interpolationSearch([],10)).toBe(-1);
21+
});
22+
});

0 commit comments

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