חיפוש אקספוננציאלי

חיפוש אקספוננציאלי
Exponential search

מחלקה	אלגוריתם חיפוש
סיבוכיות זמן	במקרה הטוב: $O(1)$, זמן ממוצע: $O(\log i)$
סיבוכיות מקום	$O(1)$

במדעי המחשב, חיפוש מעריכי (נקרא גם חיפוש כפול או חיפוש דוהר) הוא אלגוריתם, נוצר על ידי ג'ון בנטלי ואנדרו יאו ב-1976, לחיפוש ברשימות ממוינות לא חסומות/ אינסופיות. ישנן דרכים רבות ליישם את החיפוש, כאשר הנפוצה ביותר היא קביעת הטווח שבו המפתח לחיפוש נמצא, ואז ביצוע חיפוש בינארי בתוך טווח זה. סיבוכיות הזמן היא $O(\log i)$, כאשר i הוא מיקום האיבר שמחפשים ברשימה, אם הוא נמצא ברשימה, או המיקום שבו האיבר אמור להיות, אם הוא לא ברשימה.

חיפוש אקספוננציאלי יכול לשמש גם כדי לבצע חיפוש בתוך רשימות חסומות. חיפוש אקספוננציאלי יכול אפילו לתת ביצועים טובים יותר מהחיפושים הקלאסיים על רשימות חסומות, כגון חיפוש בינארי, כאשר האיבר שמחפשים קרוב יותר לתחילת המערך, היות שחיפוש אקספוננציאלי יפעל ב-$O(\log i)$ זמן, כאשר i הוא אינדקס האיבר שמחפשים ברשימה, בעוד שחיפוש בינארי ייקח $O(\log n)$ זמן, כאשר n הוא מספר האיברים ברשימה.

האלגוריתם

חיפוש אקספוננציאלי מאפשר לחפש ברשימה ממוינת, בלתי חסומה, ערך קלט (האיבר לחיפוש). האלגוריתם מורכב משני שלבים. השלב הראשון קובע טווח שבו האיבר שמחפשים צריך להיות במידה והוא נמצא ברשימה. בשלב השני, מבצעים חיפוש בינארי על טווח זה. בשלב הראשון, בהנחה שהרשימה ממוינת בסדר עולה, האלגוריתם מחפש את החזקה הראשונה, j, כך שהערך $2^{j}$ גדול יותר מהאיבר שמחפשים. ערך זה, הופך להיות הגבול העליון עבור החיפוש הבינארי, כאשר החזקה הקודמת של 2, $2^{j-1}$ היא הגבול התחתון עבור החיפוש הבינארי.

// Returns the position of key in the array arr of length size.
template <typename T>
int exponential_search(T arr[], int size, T key)
{
 if (size == 0) {
 return NOT_FOUND;
 }

 int bound = 1;
 while (bound < size && arr[bound] < key) {
 bound *= 2;
 }

 return binary_search(arr, key, bound/2, min(bound, size));
}

בכל שלב, האלגוריתם משווה את האיבר שמחפשים עם האיבר באינדקס הנוכחי. אם האיבר באינדקס הנוכחי קטן יותר מהערך שמחפשים, האלגוריתם מתבצע שוב, תוך דילוג לאינדקס הבא על ידי הכפלתו, מה שגורם לחישוב החזקה הבאה של 2. אם האיבר באינדקס הנוכחי גדול מהאיבר שמחפשים, האלגוריתם יודע עכשיו כי איבר החיפוש, אם נמצא ברשימה, ממוקם בטווח שנוצר על ידי אינדקס החיפוש הקודם, $2^{j-1}$, לאינדקס החיפוש הנוכחי, $2^{j}$. לאחר מכן מבצעים חיפוש בינארי כאשר התוצאה היא או כישלון, אם האיבר לחיפוש לא נמצא ברשימה, או המיקום של האיבר ברשימה.

ניתוח

השלב הראשון של האלגוריתם לוקח $O(\log i)$ זמן, כאשר i הוא האידקס בו האיבר לחיפוש צריך להמצא ברשימה. זה כי, בקביעת הגבול העליון עבור חיפוש בינארי, לולאת הwhile מבוצעת בדיוק $\left\lceil \log(i)\right\rceil$ פעמים. היות שהרשימה ממוינת, לאחר הכפלת אינדקס החיפוש $\left\lceil \log(i)\right\rceil$ פעמים, האלגוריתם יגיע לאינדקס חיפוש גדול או שווה לi, כיוון ש $2^{\left\lceil \log(i)\right\rceil }\geq i$. כאמור, השלב הראשון של האלגוריתם לוקח $O(\log i)$ זמן.

החלק השני של האלגוריתם גם לוקח $O(\log i)$ זמן. כיוון שהשלב השני הוא פשוט חיפוש בינארי, זה לוקח $O(\log n)$, כאשר n הוא גודל הטווח שבו מחפשים. גודל טווח זה יהיה $2^{j}-2^{j-1}$, כאשר, כפי שמופיע לעיל, $j=\log i$. זה אומר כי גודל הטווח לחיפוש הוא $2^{\log(i)}-2^{\log(i)-1}=2^{\log(i)-1}$. זה נותן לנו זמן ריצה של $\log(2^{\log(i)-1})=\log(i)-1=O(\log i)$.

סה"כ זמן הריצה הכולל של האלגוריתם, המחושב על ידי סכום זמני הריצה של שני השלבים, הוא של $O(\log i)+O(\log i)=2O(\log i)=O(\log i)$.

גרסאות נוספות

בנטלי ויאו הציעו מספר גרסאות לחיפוש אקספוננציאלי. גרסאות אלו מורכבות מביצוע חיפוש בינארי, לעומת חיפוש אונרי, לקביעת הגבול העליון של החיפוש הבינארי בשלב השני של האלגוריתם. דבר זה מחלק את השלב הראשון של האלגוריתם לשני חלקים, המסתכמים לכדי 3 שלבים של האלגוריתם בכללותו. בדומה למקודם, השלב הראשון החדש קובע ערך $j'$, כך ש $2^{j'}$ גדול יותר מהערך לחיפוש, ו-$2^{j'/2}$ קטן יותר מהערך שמחפשים. מקודם, $j'$ נקבע באמצעות חיפוש אונרי על ידי חישוב החזקה הבאה של 2 (כלומר, הוספת 1 ל-j). בגרסה זו, מוצע תחת זאת להכפיל את $j'$ (לדוגמה, לקפוץ מ$2^{2}$ ל-$2^{4}$, במקום $2^{3}$). ה-$j'$ הראשון כך ש-$2^{j'}$ גדול יותר מהערך שמחפשים, מהווה חסם עליון גס יותר ממקודם. כאשר מוצאים את $j'$, האלגוריתם עובר לשלב השני ומבצע חיפוש בינארי על הטווח בין $j'/2$ ל-$j'$, שנותן חסם עליון עליון מדויק יותר על החזקה j. מנקודה זו, השלב השלישי של האלגוריתם מבצע חיפוש בינארי על הטווח שבין $2^{j'-1}$ ל-$2^{j'}$, כמקודם. זמן הריצה של גרסה זו הוא $\lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1=O(\log i)$.

בנטלי ויאו הכלילו את הווריאציה הזו לגרסה בה מספר כלשהו, k, של חיפושים בינאריים מתבצע במהלך השלב הראשון של האלגוריתם, מה שנותן גרסה של k-חיפושים בינאריים מקוננים. זמן הריצה האסימפטוטי אינו שונה בשתי הגרסאות, פועל ב-$O(\log i)$ זמן, כמו באלגוריתם החיפוש האקספוננציאלי המקורי.

כמו כן, ניתן לתת מבנה נתונים עם גרסה חזקה של תכונת האצבע הדינמית (עץ Splay) כאשר משתמשים בתוצאה לעיל של k- חיפושים בינאריים מקוננים על מערך ממוין. תוך שימוש במבנה נתונים זה, מספר ההשוואות שמבוצעות במהלך חיפוש הוא $\log(d)+\log \log(d)+...+O(\log ^{*}(d))$, כאשר d הוא ההפרש בדרגה בין האיבר האחרון שהתבצעה גישה אליו והאיבר הנוכחי שנגשים אליו.

לקריאה נוספת

• חיפוש ליניארי
• חיפוש בינארי
• חיפוש אינטרפולציה
• חיפוש משולש
• טבלת גיבוב

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34572806חיפוש אקספוננציאלי