אלגוריתם חיפוש

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

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

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

אלגוריתם חיפוש הוא דרך למצוא פריט במחשב.
מבנה נתונים הוא איך מסדרים את הפריטים.

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

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