איך בונים אלגוריתם חיפוש?

חיפוש הוא סריקה של מערך נתונים כדי למצוא בו ערך כלשהו על פי קריטריון חיפוש כלשהו. הבעיה בחיפוש הוא ככל שננהל טבלאות או קבצים גדולים יותר כך ירבה הזמן אותו יבזבז המחשב כדי למצוא נתון מסוים. נדגים פה מספר שיטות חיפוש, מוסברות כאלגוריתם מילולי ומתורגמות לשפת התכנות פסקל.

חיפוש סדרתי הוא החיפוש הנפוץ והפשוט ביותר. חיפוש זה מתאים לכל מבני הנתונים. דוגמה לחיפוש זה כאשר אנו מחפשים בטבלה את הערך key, כאשר אנו מוצאים אותו, אנו נעביר למשתנה Position את מיקומו בטבלה:

Position := -1;
For I := 1 to Size do
If Table[I] = Key then Position := I;

Position := -1;
I := 1;
While (I <= Size) and (Table [I] <> Key)
do I := I + 1;
If I <= Size then Position := I;

החיפוש הבינארי הוא חיפוש המאפשר יעילות רבה יותר בתהליכי החיפוש. בשיטה זו אנו מתבססים על העובדה שמערך הנתונים שלנו ממוין. זהו יתרונה של השיטה שהחיפוש הוא יותר יעיל מחיפוש סדרתי, אך גם חסרונו בכך שהמערך חייב להיות ממוין לפני הפעלת החיפוש.

הדגמת השיטה: נדמה טבלה של מספרים ממוינת ואנו מחפשים מספר מסוים - a. בשיטה זו ניגש תחילה לאיבר האמצעי במערך ונשווה אותו ל-a. אם הוא שווה לו - מצאנו את האיבר ואז החיפוש מסתיים. אם הערך גדול מ-a נתמקד בחצי הטבלה הנמוכה מהאמצע, ואז לא נתמקד בחצי הגבוה. שוב נפעיל את אותה שיטה ונפנה לאיבר האמצעי עכשיו (האיבר האמצעי בחצי הטבלה שמצאנו) ונשווה אותו ל-a. נחלק את הטבלה שוב ונתמקד בחלק הטבלה שהאיבר a עשוי להימצא בו. החיפוש יסתיים כאשר נמצא את האיבר, או שהאיבר לא נמצא - ואז נגלה שלא נוכל לחלק עוד את הטבלה.
קטע תוכנית לדוגמה בשפת התכנות פסקל:

Key := a;
Low := 1;
High := Size;
Repeat
I := (Low + High) div 2;
If Table[I] < Key then Low := I;
If Table[I] > Key then High := I;
Until (Table[I] = Key) Or (Low = High);
Position := I;

מה קשור?

מהן פקודות דוס?  איך מחפשים באינטרנט?  איך בונים אלגוריתם מיון?

 

 הוסף הערה חדשה    שנה את ההגדרות בנוגע להערות