Problem 56070. Jump Search - 02

Created by Asif Newaz

Solve Later

Find the number of leaps you need to take to find the 'first occurrence' of an element in an array using the jump search algorithm.
For example, 
a=[ 2,5,6,9,12,15,15,16,17,19,31]
To find 16 with a jump step of 3, you follow,  2 -> 9 -> 15 -> 19 -> 17 -> 16
So, total number of jumps = 5
n.b. to go forward, you take n-step jump; to go backwards, you jump only one step back. 
In this problem, you will have repetition of numbers. you need to find the index of the first occurence. 
The array is always sorted. But you need to look out and go backward even after finding the element to ensure it is the first occurence.
If the jump step is larger than the array size, u directly go to the last element of the array

Solve

Solution Stats

22 Solutions
4 Solvers

Last Solution submitted on Aug 03, 2024

Last 200 Solutions

Problem Comments

6 Comments

6 Comments

Show 3 older comments

William on 29 Sep 2022

I believe that the values in Tests 7, 9 and 10 are incorrect.

Ramy Salem on 29 Sep 2022

I agree with William, Tests 7,9 and 10 need review

Asif Newaz on 29 Sep 2022

thanks for pointing it out.
Test case 7 was wrong - x and n values were interchanged. it has been fixed.

However, in test cases 9 and 10 -

a=[5, 10, 10, 10, 25, 30, 35, 35, 55, 65, 100, 600, 4000, 10000, 10000, 30000, 30000, 48000];
x=35;
n=2;

5-->10-->25-->35-->30. so 4 jumps.
since repetition is possible and you have to find the first occurrence, you do not know for sure once you reach 35 whether it is the first time it appeared. so u need to go backward to check whether it had appeared before till the previous jump point.

Same for test case 10.
hope it clarifies.

William on 29 Sep 2022

Oh! Clever!
But by the same reasoning, I would expect the following tests need correction, because they all need to check for a prior duplicate:
Test 4: y_correct = 2 2->31->19
Test 5: y_correct = 4 2->31->19->17->16
Test 10: y_correct = 3 5->10->35->30
Also, Test 3 should be changed to y_correct=0, as it was in the previous Jump_Search problem

Asif Newaz on 30 Sep 2022

sorry for the mistakes - I put this problem in haste.
I have checked all the test cases now - hopefully, everything is okay now.
i have also updated the problem definition

William on 30 Sep 2022

Thanks Asif! This is a surprisingly tricky problem and I enjoyed it very much.

Solution Comments

Show comments

Problem Recent Solvers4

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 56070. Jump Search - 02

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Problem 56070. Jump Search - 02

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Players