Đang tải…
Đang tải…
Giống tìm kiếm nhị phân nhưng ước lượng vị trí dò từ giá trị target — gần O(log log n) trên dữ liệu phân bố đều.
Ước lượng vị trí của 53 bằng nội suy.
Mẹo: bấm vào một cột để chọn nó làm mục tiêu.
1int interpolationSearch(int[] a, int target) {2 int lo = 0, hi = a.length - 1;3 while (lo <= hi && target >= a[lo] && target <= a[hi]) {4 int pos = lo + (target-a[lo])*(hi-lo)/(a[hi]-a[lo]);5 if (a[pos] == target) return pos;6 else if (a[pos] < target) lo = pos + 1;7 else hi = pos - 1;8 }9 return -1;10}