Đang tải…
Đang tải…
Trên mảng đã sắp xếp, nhảy theo khối cố định √n cho đến khi vượt qua target, rồi quét tuyến tính trong khối cuối.
Nhảy theo khối √n = 3 để tìm 53.
Mẹo: bấm vào một cột để chọn nó làm mục tiêu.
1int jumpSearch(int[] a, int target) {2 int n = a.length, step = (int)Math.sqrt(n), prev = 0;3 while (prev < n && a[Math.min(step, n)-1] < target) {4 prev = step; step += (int)Math.sqrt(n);5 if (prev >= n) return -1;6 }7 for (int i = prev; i < Math.min(step, n); i++)8 if (a[i] == target) return i;9 return -1;10}