+ 4

In binary search, why jump back is cost?

My question comes from the following paragraph. Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps, consider a situation where the element to be searched is the smallest element or smaller than the smallest). So in a system where binary search is costly, we use Jump Search. Here is what jump search about: http://geeksforgeeks.org/jump-search/ And why jump forward doesn't cost as well?

20th Oct 2019, 11:06 AM
Merida
Merida - avatar
5 Answers
+ 6
By jump back, I think they mean that the sorting operation goes on again. Like, you have a set of N elements and you look through all of them in order. After that, you come back to the start and look through them all. That's what jump back means.
20th Oct 2019, 11:20 AM
👑 Prometheus 🇸🇬
👑 Prometheus 🇸🇬 - avatar
+ 2
Gotcha ... Ur question is why jumping forward is not costly... While jumping backward is costly... Well ... In simple terms ... You jump forward and then comeback to search is more time consuming than jumping forward n searching.
21st Oct 2019, 7:25 AM
stephen haokip
stephen haokip - avatar
+ 1
here is my jumpsearch i tried to make as simple as possible public class JumpSearch{ public static void jumpsearch(int[] arr, int x){ int index = 0; boolean found = false; int rightindex = 0; int prevrightindex = 0; int jump = (int)Math.sqrt(arr.length); if(arr.length == 0){ System.out.println("The array is empty"); } if(arr[0] == x){ found = true; } while(rightindex < arr.length - 1){ rightindex = Math.min(arr.length - 1, jump + rightindex); if(x <= arr[rightindex]){ break; } prevrightindex = rightindex; } if(rightindex == arr.length -1 && x > arr[rightindex] && x < arr[rightindex]){ found = false; } for(int i = rightindex; i > prevrightindex; i--){ if(arr[i] == x){ found = true; index = i; break; } } if(found == true){ System.out.println("Element(x) found at index "+index+"."); } else{ System.out.println("Element(x) does not exist in the array."); } } public static void main(String[] args){ int[] arr = {11,22,33,44,55,66,77,88,99}; int x = 989; jumpsearch(arr, x); } } i too noticed that in most code on jump search if we search for an element(x) lesser than the smallest element or larger than the largest element. the output is either -1 or something else thats confusing for beginners so i made the above code.
21st Oct 2019, 6:14 AM
stephen haokip
stephen haokip - avatar
+ 1
stephen haokip click the link in my post, the jump search code in it is fine.
21st Oct 2019, 7:05 AM
Merida
Merida - avatar
0
Prometheus [EXAMS]🇸🇬 🤔, I don't really understand. But isn't accessing array element is directly (fast) ?
20th Oct 2019, 12:08 PM
Merida
Merida - avatar