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

Commita327b68

Browse files
committed
Add Jump Search algorithm.
1 parentb73ddec commita327b68

File tree

8 files changed

+114
-0
lines changed

8 files changed

+114
-0
lines changed

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,6 +84,7 @@ a set of rules that precisely define a sequence of operations.
8484
*`A`[Regular Expression Matching](src/algorithms/string/regular-expression-matching)
8585
***Searches**
8686
*`B`[Linear Search](src/algorithms/search/linear-search)
87+
*`B`[Jump Search](src/algorithms/search/jump-search)
8788
*`B`[Binary Search](src/algorithms/search/binary-search)
8889
***Sorting**
8990
*`B`[Bubble Sort](src/algorithms/sorting/bubble-sort)
@@ -129,6 +130,7 @@ of algorithms. It is an abstraction higher than the notion of an algorithm, just
129130
algorithm is an abstraction higher than a computer program.
130131

131132
***Brute Force** - look at all the possibilities and selects the best solution
133+
*`B`[Linear Search](src/algorithms/search/linear-search)
132134
*`A`[Maximum Subarray](src/algorithms/sets/maximum-subarray)
133135
*`A`[Travelling Salesman Problem](src/algorithms/graph/travelling-salesman) - shortest possible route that visits each city and returns to the origin city
134136
***Greedy** - choose the best option at the current time, without any consideration for the future

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,11 @@ in the array.
1212

1313
![Binary Search](https://upload.wikimedia.org/wikipedia/commons/8/83/Binary_Search_Depiction.svg)
1414

15+
##Complexity
16+
17+
**Time Complexity**:`O(log(n))` - since we split search area by two for every
18+
next iteration.
19+
1520
##References
1621

1722
-[Wikipedia](https://en.wikipedia.org/wiki/Binary_search_algorithm)

‎src/algorithms/search/binary-search/binarySearch.js‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
importComparatorfrom'../../../utils/comparator/Comparator';
22

33
/**
4+
* Binary search implementation.
5+
*
46
*@param {*[]} sortedArray
57
*@param {*} seekElement
68
*@param {function(a, b)} [comparatorCallback]
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#Jump Search
2+
3+
Like Binary Search,**Jump Search** (or**Block Search**) is a searching algorithm
4+
for sorted arrays. The basic idea is to check fewer elements (than linear search)
5+
by jumping ahead by fixed steps or skipping some elements in place of searching all
6+
elements.
7+
8+
For example, suppose we have an array`arr[]` of size`n` and block (to be jumped)
9+
of size`m`. Then we search at the indexes`arr[0]`,`arr[m]`,`arr[2 * m]`, ...,`arr[k * m]` and
10+
so on. Once we find the interval`arr[k * m] < x < arr[(k+1) * m]`, we perform a
11+
linear search operation from the index`k * m` to find the element`x`.
12+
13+
**What is the optimal block size to be skipped?**
14+
In the worst case, we have to do`n/m` jumps and if the last checked value is
15+
greater than the element to be searched for, we perform`m - 1` comparisons more
16+
for linear search. Therefore the total number of comparisons in the worst case
17+
will be`((n/m) + m - 1)`. The value of the function`((n/m) + m - 1)` will be
18+
minimum when`m = √n`. Therefore, the best step size is`m = √n`.
19+
20+
##Complexity
21+
22+
**Time complexity**:`O(√n)` - because we do search by blocks of size`√n`.
23+
24+
##References
25+
26+
-[Wikipedia](https://en.wikipedia.org/wiki/Jump_search)
27+
-[GeeksForGeeks](https://www.geeksforgeeks.org/jump-search/)
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
importjumpSearchfrom'../jumpSearch';
2+
3+
describe('jumpSearch',()=>{
4+
it('should search for an element in sorted array',()=>{
5+
expect(jumpSearch([],1)).toBe(-1);
6+
expect(jumpSearch([1],2)).toBe(-1);
7+
expect(jumpSearch([1],1)).toBe(0);
8+
expect(jumpSearch([1,2],1)).toBe(0);
9+
expect(jumpSearch([1,2],1)).toBe(0);
10+
expect(jumpSearch([1,1,1],1)).toBe(0);
11+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],2)).toBe(1);
12+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],0)).toBe(-1);
13+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],0)).toBe(-1);
14+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],7)).toBe(-1);
15+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],5)).toBe(2);
16+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],20)).toBe(4);
17+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],30)).toBe(7);
18+
expect(jumpSearch([1,2,5,10,20,21,24,30,48],48)).toBe(8);
19+
});
20+
});
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
importComparatorfrom'../../../utils/comparator/Comparator';
2+
3+
/**
4+
* Jump (block) search implementation.
5+
*
6+
*@param {*[]} sortedArray.
7+
*@param {*} seekElement
8+
*@param {function(a, b)} [comparatorCallback]
9+
*@return {number}
10+
*/
11+
exportdefaultfunctionjumpSearch(sortedArray,seekElement,comparatorCallback){
12+
constcomparator=newComparator(comparatorCallback);
13+
constarraySize=sortedArray.length;
14+
15+
if(!arraySize){
16+
// We can't find anything in empty array.
17+
return-1;
18+
}
19+
20+
// Calculate optimal jump size.
21+
// Total number of comparisons in the worst case will be ((arraySize/jumpSize) + jumpSize - 1).
22+
// The value of the function ((arraySize/jumpSize) + jumpSize - 1) will be minimum
23+
// when jumpSize = √array.length.
24+
constjumpSize=Math.floor(Math.sqrt(arraySize));
25+
26+
// Find the block where the seekElement belong to.
27+
letblockStart=0;
28+
letblockEnd=jumpSize;
29+
while(comparator.greaterThan(seekElement,sortedArray[Math.min(blockEnd,arraySize)-1])){
30+
// Jump to the next block.
31+
blockStart=blockEnd;
32+
blockEnd+=jumpSize;
33+
34+
// If our next block is out of array then we couldn't found the element.
35+
if(blockStart>arraySize){
36+
return-1;
37+
}
38+
}
39+
40+
// Do linear search for seekElement in subarray starting from blockStart.
41+
letcurrentIndex=blockStart;
42+
while(currentIndex<Math.min(blockEnd,arraySize)){
43+
if(comparator.equal(sortedArray[currentIndex],seekElement)){
44+
returncurrentIndex;
45+
}
46+
47+
currentIndex+=1;
48+
}
49+
50+
return-1;
51+
}

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,11 @@ comparisons, where `n` is the length of the list.
88

99
![Linear Search](https://www.tutorialspoint.com/data_structures_algorithms/images/linear_search.gif)
1010

11+
##Complexity
12+
13+
**Time Complexity**:`O(n)` - since in worst case we're checking each element
14+
exactly once.
15+
1116
##References
1217
-[Wikipedia](https://en.wikipedia.org/wiki/Linear_search)
1318
-[TutorialsPoint](https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm)

‎src/algorithms/search/linear-search/linearSearch.js‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
importComparatorfrom'../../../utils/comparator/Comparator';
22

33
/**
4+
* Linear search implementation.
5+
*
46
*@param {*[]} array
57
*@param {*} seekElement
68
*@param {function(a, b)} [comparatorCallback]

0 commit comments

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