חיפוש בינארי לעומת חיפוש לינארי
חיפוש לינארי, הידוע גם בשם החיפוש הרציף הוא אלגוריתם החיפוש הפשוט ביותר. הוא מחפש ערך שצוין ברשימה על ידי בדיקת כל רכיב ברשימה. חיפוש בינארי הוא גם שיטה המשמשת לאיתור ערך מוגדר ברשימה ממוינת. שיטת חיפוש בינארי מפחיתה בחצי את מספר האלמנטים שנבדקו (בכל איטרציה), ומפחיתה את הזמן שלוקח לאיתור הפריט הנתון ברשימה.
מהו חיפוש לינארי?
חיפוש לינארי הוא שיטת החיפוש הפשוטה ביותר, שבודקת כל רכיב ברשימה ברצף עד שהיא מוצאת אלמנט מוגדר.הקלט לשיטת החיפוש הליניארי הוא רצף (כגון מערך, אוסף או מחרוזת) והפריט שצריך לחפש. הפלט נכון אם הפריט שצוין נמצא ברצף שסופק או false אם הוא לא ברצף. מכיוון ששיטה זו בודקת כל פריט ברשימה עד למציאת הפריט שצוין, במקרה הגרוע היא תעבור על כל האלמנטים ברשימה לפני שתמצא את האלמנט הנדרש. המורכבות של החיפוש הליניארי היא o(n). לכן הוא נחשב לאיטי מדי לשימוש בעת חיפוש אלמנטים ברשימות גדולות. אבל זה מאוד פשוט וקל יותר ליישום.
מהו חיפוש בינארי?
חיפוש בינארי הוא גם שיטה המשמשת לאיתור פריט מוגדר ברשימה ממוינת. שיטה זו מתחילה בהשוואה בין האלמנט המחפש לאלמנטים שבאמצע הרשימה. אם ההשוואה קובעת ששני האלמנטים שווים השיטה נעצרת ומחזירה את מיקום האלמנט. אם האלמנט המחפש גדול מהאלמנט האמצעי, הוא מתחיל את השיטה שוב באמצעות החצי התחתון של הרשימה הממוינת בלבד.אם האלמנט המחפש קטן מהאלמנט האמצעי, הוא מתחיל את השיטה שוב באמצעות החצי העליון של הרשימה הממוינת בלבד. אם האלמנט המחפש אינו ברשימה, השיטה תחזיר ערך ייחודי המציין זאת. לכן שיטת החיפוש הבינארי מפחיתה בחצי את מספר האלמנטים בהשוואה (בכל איטרציה), בהתאם לתוצאת ההשוואה. כתוצאה מכך, חיפוש בינארי פועל בזמן לוגריתמי וכתוצאה מכך ביצועי מקרה ממוצע של o(log n).
מה ההבדל בין חיפוש בינארי לחיפוש לינארי?
למרות שגם חיפוש ליניארי וגם חיפוש בינארי הם שיטות חיפוש יש להם כמה הבדלים. בעוד שחיפוש בינארי פועל על רשימות ממוינות, חיפוש אניה יכול לפעול גם על רשימות לא ממוינות. למיון רשימה יש בדרך כלל מורכבות מקרה ממוצעת של n log n. חיפוש לינארי הוא פשוט ופשוט ליישום מאשר החיפוש הבינארי. אבל, חיפוש לינארי איטי מדי לשימוש עם רשימות גדולות בגלל ביצועי המקרים הממוצעים שלו.מצד שני, חיפוש בינארי נחשב לשיטה יעילה יותר שניתן להשתמש בה עם רשימות גדולות. אבל יישום החיפוש הבינארי עשוי להיות די מסובך ומחקר הראה שניתן למצוא את הקוד המדויק לחיפוש בינארי רק בחמישה מתוך עשרים ספרים.
