In binary search, why jump back is cost?

Question

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?

Answer 1

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.

Answer 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.

Answer 3

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.

Answer 4

stephen haokip
click the link in my post, the jump search code in it is fine.

Answer 5

Prometheus [EXAMS]🇸🇬 🤔, I don't really understand.
But isn't accessing array element is directly (fast) ?