Đang tải…
Đang tải…
Nhân đôi cận chỉ số cho đến khi vượt target, rồi tìm nhị phân trong khoảng đó — rất hợp cho dữ liệu sắp xếp rất lớn hoặc không biết kích thước.
Kiểm tra a[0] = 6 trước.
Mẹo: bấm vào một cột để chọn nó làm mục tiêu.
1int exponentialSearch(int[] a, int target) {2 if (a[0] == target) return 0;3 int n = a.length, bound = 1;4 while (bound < n && a[bound] < target) bound *= 2;5 int lo = bound/2, hi = Math.min(bound, n-1);6 while (lo <= hi) {7 int mid = (lo + hi) / 2;8 if (a[mid] == target) return mid;9 else if (a[mid] < target) lo = mid + 1;10 else hi = mid - 1;11 }12 return -1;13}