Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why can't we use binary search in jump search instead of linear search?

Tags:

The following article explains Jump Search:

http://www.geeksforgeeks.org/jump-search/

The last step is a linear search. Why can't we use binary search if the array is already sorted and time complexity of binary search is log(n) while of the linear search it is n?

like image 503
Simran Avatar asked May 28 '17 15:05

Simran


1 Answers

The use case for jump search (O(√n)) over binary search (O(log n)) is when jumping back is expensive. Replacing the linear search in jump search would be counterproductive in that regard.

like image 124
David Eisenstat Avatar answered Sep 24 '22 10:09

David Eisenstat