Problem 56070. Jump Search - 02
- 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
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.
Solution Comments
Show commentsProblem Recent Solvers4
Suggested Problems
-
606 Solvers
-
307 Solvers
-
Replace secondary diagonal elements of a square array
162 Solvers
-
Find the sides of an isosceles triangle when given its area and height from its base to apex
1925 Solvers
-
148 Solvers
More from this Author165
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!