| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
1 parent 5753f46 commit bdbbece
1 file changed
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -12,26 +12,50 @@ | |||
| 12 | 12 | * Once the range is found, a linear search is performed within that block. | |
| 13 | 13 | * | |
| 14 | 14 | * <p> | |
| 15 | - * The Jump Search algorithm is particularly effective for large sorted arrays where the cost of | ||
| 16 | - * performing a linear search on the entire array would be prohibitive. | ||
| 15 | + * <b>How it works:</b> | ||
| 16 | + * <ol> | ||
| 17 | + * <li>Calculate the optimal block size as √n (square root of array length)</li> | ||
| 18 | + * <li>Jump ahead by the block size until the current element is greater than the target</li> | ||
| 19 | + * <li>Perform a linear search backwards within the identified block</li> | ||
| 20 | + * </ol> | ||
| 17 | 21 | * | |
| 18 | 22 | * <p> | |
| 19 | - * Worst-case performance: O(√N)<br> | ||
| 20 | - * Best-case performance: O(1)<br> | ||
| 21 | - * Average performance: O(√N)<br> | ||
| 22 | - * Worst-case space complexity: O(1) | ||
| 23 | + * <b>Example:</b><br> | ||
| 24 | + * Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], Target: 9<br> | ||
| 25 | + * Step 1: Jump from index 0 → 3 → 6 (9 < 13, so we found the block)<br> | ||
| 26 | + * Step 2: Linear search from index 3 to 6: found 9 at index 4<br> | ||
| 27 | + * Result: Index = 4 | ||
| 28 | + * | ||
| 29 | + * <p> | ||
| 30 | + * <b>Time Complexity:</b><br> | ||
| 31 | + * - Best-case: O(1) - element found at first position<br> | ||
| 32 | + * - Average: O(√n) - optimal block size reduces jumps<br> | ||
| 33 | + * - Worst-case: O(√n) - element at end of array or not present<br> | ||
| 34 | + * | ||
| 35 | + * <p> | ||
| 36 | + * <b>Space Complexity:</b> O(1) - only uses a constant amount of extra space | ||
| 37 | + * | ||
| 38 | + * <p> | ||
| 39 | + * <b>Note:</b> Jump Search requires a sorted array. For unsorted arrays, use Linear Search. | ||
| 40 | + * Compared to Linear Search (O(n)), Jump Search is faster for large arrays. | ||
| 41 | + * Compared to Binary Search (O(log n)), Jump Search is less efficient but may be | ||
| 42 | + * preferable when jumping through a linked list or when backward scanning is costly. | ||
| 23 | 43 | * | |
| 24 | 44 | * <p> | |
| 25 | 45 | * This class implements the {@link SearchAlgorithm} interface, providing a generic search method | |
| 26 | 46 | * for any comparable type. | |
| 47 | + * | ||
| 48 | + * @see SearchAlgorithm | ||
| 49 | + * @see BinarySearch | ||
| 50 | + * @see LinearSearch | ||
| 27 | 51 | */ | |
| 28 | 52 | public class JumpSearch implements SearchAlgorithm { | |
| 29 | 53 | ||
| 30 | 54 | /** | |
| 31 | 55 | * Jump Search algorithm implementation. | |
| 32 | 56 | * | |
| 33 | - * @param array the sorted array containing elements | ||
| 34 | - * @param key the element to be searched | ||
| 57 | + * @param array the sorted array containing elements (must be sorted in ascending order) | ||
| 58 | + * @param key the element to be searched for | ||
| 35 | 59 | * @return the index of {@code key} if found, otherwise -1 | |
| 36 | 60 | */ | |
| 37 | 61 | @Override | |
| Back | FazBrowse Home | New Git URL |
0 commit comments