Continuing our recent dive into search algorithms, we will now be covering the Jump Search algorithm. Similar toBinary Search the Jump Search algorithm is a searching algorithm for pre-sorted arrays.

The basic idea is to check fewer elements thanLinear Search byjumping ahead by a fixed increment and backtracking when a larger value than the one searched for is found, running aLinear Search from there to find if the value exists. This may sound strange at first but by the end of this article, all will be clear.

This algorithm saves time and is thus faster when compared to aLinear Search since we do not look at all elements in the collection. It is however slower thanBinary Search since the Jump Search algorithm runs with a best caseBig O ofO(√n).

Jump search has one advantage overBinary Search however and that is that we only go backwards once whereasBinary Search can jump back as many asO(Log n) times. This being the case, in situations whereBinary Search seems to be running slow due to backward lookups, Jump Search might be able to help you in such a scenario to speed things up.

Tests

frommainimportjumpSearch;deftest_strings():assertjumpSearch(["Dave","James"],"Dave")==0;assertjumpSearch(["Dave","James"],"abc")==-1;deftest_integers():assertjumpSearch([1,2,3,4],3)==2;assertjumpSearch([1,2,3,4],5)==-1;deftest_floats():assertjumpSearch([3.14],3.14)==0;assertjumpSearch([3.141],3.14)==-1;deftest_booleans():assertjumpSearch([False,True],True)==1;assertjumpSearch([False,True],False)==0;deftest_lists():assertjumpSearch([[3.14]],[3.14])==0;assertjumpSearch([[3.141]],[3.14])==-1;deftest_nested_lists():assertjumpSearch([[3.14,[1]]],[3.14,[1]])==0;assertjumpSearch([[3.141]],[3.14])==-1;deftest_sets():assertjumpSearch([set([1])],set([1]))==0;assertjumpSearch([set([1])],set([1,2]))==-1;deftest_tuples():assertjumpSearch([tuple([1])],tuple([1]))==0;assertjumpSearch([tuple([1])],tuple([1,2]))==-1;

You may notice that these are similar to the tests forLinear Search andBinary Search that we wrote in previous articles and this is on purpose.

The difference in tests comes, as with binary search, in thecomparison operators we are using. In our case the tests fordict were removed and the test forboolean vsNone have also been removed. These are not possible to have due to these not being able to compare to one another using the less than (<) operator which is used in the Jump Search algorithm implementation.

You can run and explore through the tests via the repl below:

Implementation

frommathimportsqrt;fromtypingimportList,TypeVar;fromoperatorimporteqasdeep_equals,geasgreater_than_or_equal,neasnot_equal,ltasless_than;T=TypeVar('T')deflinearSearch(collection:List[T],value:T)->int:forindex,iteminenumerate(collection):ifdeep_equals(item,value):returnindex;return-1;defjumpSearch(collection:List[T],value:T)->int:n=len(collection);step=sqrt(n);prev=0;whileless_than(collection[int(min(step,n)-1)],value):prev=step;step*=2;ifgreater_than_or_equal(prev,n):return-1;foundIndex=linearSearch(collection[int(prev):],value);ifnot_equal(foundIndex,-1):foundIndex+=int(prev);returnfoundIndex;

Note 1: Since Jump Search utilisesLinear Search, we will use the implementation we built previously in this article series for that.

For thejumpSearch function, we require acollection and avalue to be provided and will return anint (integer) representing the index of thevalue if it is found and-1 if it is not. Thevalue itself is what we will be looking for in thecollection.

Note 2: Thecollection should be aList of items matching the same type as thevalue we are searching for and thus, if thevalue is of typestr (string) then we expect thecollection to be aList[str] for example.

Whence we enter thejumpSearch function body, we declare 3 variables:

1. The variablen to represent the amount of items in thecollection
2. The variablestep to be the value of how far we shouldjump each time, this is defined as thesquare root ofn
3. The variableprev to represent the last index visited when the laststep was taken

From here we run awhile loop as long as the current item atint(min(step, n) - 1) is less than thevalue we are searching for. You may be wondering why we useint(min(step, n) - 1). Let's break it down from the inside out. Let's use the first iteration of thewhile loop for aPseudocode example:

collection=[1,2,3];value=2;n=len(collection);# 3step=sqrt(n);# 1.73205080757prev=0;# 0nextIndex=min(step,n)-1;# 0.73205080757indexAsInteger=int(nextIndex)# 0itemAtIndex=collection[indexAsInteger];# 1condition=less_than(itemAtIndex,value);# TruewhileconditionisTrue:# now we run the loop since the condition is True

That is the essential breakdown of thewhile loops condition and hopefully that makes sense as to why we runint(min(step, n) - 1) in the implementation now.

Inside the loop we set theprev to equal the currentstep and then add thestep to itself for the next iteration of thewhile loop. During the loop execution we check that theprev variable is not greater than or equal to the length of thecollection which we stored in the variablen. If it is, we haven't found thevalue in thecollection and return-1 to represent that it wasn't found.

If we exit the loop and didn't return-1, we must have thevalue still in thecollection and so we then run thelinearSearch function with a new array created from a slice of thecollection running from theprev step index to the end of the collection and pass in thevalue we are looking for also. If thelinearSearch run doesn't return-1, we have found thevalue and all we need to do is add theprev step index value to thefoundIndex.

Note 3: We do this because if-1 wasn't returned and thus thevalue was found. If you remember we took a slice of thecollection beginning from theprev step to the end of thecollection for thelinearSearch to run over and thus if the value was found bylinearSearch at index1 then it would be in thecollection at indexprev + 1.

This works well for us since we return thefoundIndex either way and so if thevalue is not found we will just return the-1 anyway.

Conclusions

Jump Search is useful in places whereBinary Search is potentially slow due to backwards lookups. It is faster than a regularLinear Search and tries to maximise efficiency by using jumps through the sorted collection.

I hope you found some value in this article and if you have any questions or comments, feel free to write them below!