Đang tải…
Đang tải…
Chia khoảng thành ba phần với hai điểm dò mỗi vòng — cùng bậc với binary search, nhưng nhiều phép so sánh hơn.
Đang tìm 53. Ternary search giữ hai điểm dò thay vì một, chia khoảng đang xét thành ba phần.
Mẹo: bấm vào một cột để chọn nó làm mục tiêu.
1int ternarySearch(int[] a, int target) {2 int lo = 0, hi = a.length - 1;3 while (lo <= hi) {4 int third = (hi - lo) / 3;5 int m1 = lo + third, m2 = hi - third;6 if (a[m1] == target) return m1;7 if (a[m2] == target) return m2;8 if (target < a[m1]) hi = m1 - 1;9 else if (target > a[m2]) lo = m2 + 1;10 else { lo = m1 + 1; hi = m2 - 1; } // một phần ba giữa11 }12 return -1;13}