Đ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[] arr, int target) {2 int n = arr.length, step = (int)Math.sqrt(n), prev = 0; // Khối cỡ √n3 while (prev < n && arr[Math.min(step, n)-1] < target) { // Cuối khối < target4 prev = step; step += (int)Math.sqrt(n); // Nhảy một khối5 if (prev >= n) return -1; // Vượt cuối mảng6 }7 for (int i = prev; i < Math.min(step, n); i++) // Quét khối tuyến tính8 if (arr[i] == target) return i; // Tìm thấy9 return -1; // Không có trong mảng10}