کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431269 688489 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Adaptive search over sorted sets
ترجمه فارسی عنوان
جستجوی سازگار با مجموعه های مرتب شده
کلمات کلیدی
مرتب سازی، جستجو مجموعه های مرتب شده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We revisit the classical algorithms for searching over sorted sets to introduce an algorithm refinement, called Adaptive search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Interpolation search, only a constant number of extra comparisons is introduced. Yet, under diverse input data distributions our algorithm shows costs comparable to that of Interpolation search, i.e., O(log⁡log⁡n)O(log⁡log⁡n) while the worst-case cost is always in O(log⁡n)O(log⁡n), as with Binary search. On benchmarks drawn from large datasets, both synthetic and real-life, Adaptive search scores better times and lesser memory accesses even than Santoro and Sidney's Interpolation–Binary search.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 30, January 2015, Pages 128–133
نویسندگان
, , , , ,