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
Solution Stats
Problem Comments
6 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers4
Suggested Problems
-
Return the first and last characters of a character array
11819 Solvers
-
Add a row of zeros on top of a matrix
268 Solvers
-
Side of an equilateral triangle
6875 Solvers
-
60 Solvers
-
6268 Solvers
More from this Author174
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
I believe that the values in Tests 7, 9 and 10 are incorrect.
I agree with William, Tests 7,9 and 10 need review
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.
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
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
Thanks Asif! This is a surprisingly tricky problem and I enjoyed it very much.