לפני שנבין את ההבדלים בין החיפוש הליניארי לבינארי, עלינו להכיר תחילה את החיפוש הליניארי והחיפוש הבינארי בנפרד.

מהו חיפוש לינארי?

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

בואו נבחן דוגמה פשוטה.

נניח שיש לנו מערך של 10 אלמנטים כפי שמוצג באיור שלהלן:

האיור שלמעלה מציג מערך של סוג תווים בעל 10 ערכים. אם אנחנו רוצים לחפש 'E', החיפוש מתחיל מה-0^ה'אלמנט וסורק כל אלמנט עד שהאלמנט, כלומר 'E' לא נמצא. אנחנו לא יכולים לקפוץ ישירות מה-0^ה'אלמנט ל-4^ה'אלמנט, כלומר, כל אלמנט נסרק אחד אחד עד שהאלמנט לא נמצא.

המורכבות של חיפוש לינארי

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

מהו חיפוש בינארי?

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

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

ישנם שלושה מקרים בשימוש בחיפוש הבינארי:

מקרה 1: נתונים

מקרה 2: data>a[mid] ואז right=mid-1

מקרה 3: נמצא אלמנט = a[mid] //

במקרה הנ'ל,' א ' זה שם המערך, בֵּינוֹנִי הוא האינדקס של האלמנט המחושב באופן רקורסיבי, נתונים הוא האלמנט שיש לחפש, שמאלה מציין את האלמנט השמאלי של המערך ו ימין מציין את האלמנט המתרחש בצד ימין של המערך.

בואו נבין את פעולת החיפוש הבינארי באמצעות דוגמה.

נניח שיש לנו מערך בגודל של 10 שמצויד באינדקס מ-0 עד 9 כפי שמוצג באיור שלהלן:

אנו רוצים לחפש אלמנט 70 מהמערך שלמעלה.

שלב 1: ראשית, אנו מחשבים את האלמנט האמצעי של מערך. אנו רואים שני משתנים, כלומר שמאל וימין. בתחילה, שמאל = 0 וימין = 9 כפי שמוצג באיור שלהלן:

ניתן לחשב את ערך האלמנט האמצעי כך:

לכן, mid = 4 ו-a[mid] = 50. האלמנט שיש לחפש הוא 70, כך ש-a[mid] אינו שווה לנתונים. מקרה 2 מסופק, כלומר, data>a[mid].

שלב 2: בתור data>a[mid], כך הערך של left גדל ב-mid+1, כלומר, left=mid+1. הערך של mid הוא 4, כך שהערך של left הופך ל-5. כעת, יש לנו תת-מערך כפי שמוצג באיור שלהלן:

עכשיו שוב, הערך האמצעי מחושב באמצעות הנוסחה לעיל, והערך של אמצע הופך ל-7. כעת, האמצע יכול להיות מיוצג כך:

באיור שלמעלה, אנו יכולים לראות ש-a[mid]>data, אז שוב, הערך של mid יחושב בשלב הבא.

שלב 3: כנתונים[mid]>, ערך הזכות מופחת באמצע-1. הערך של mid הוא 7, כך שהערך של ימין הופך ל-6. ניתן לייצג את המערך כך:

הערך של mid יחושב שוב. הערכים של שמאל וימין הם 5 ו-6, בהתאמה. לכן, הערך של mid הוא 5. כעת ניתן לייצג את האמצע במערך כפי שמוצג להלן:

באיור שלעיל, אנו יכולים לראות כי [אמצע]

שלב 4: כ[אמצע]

כעת הערך של mid מחושב שוב באמצעות הנוסחה שכבר דנו בה. הערכים של שמאל וימין הם 6 ו-6 בהתאמה, כך שהערך של mid הופך ל-6 כפי שמוצג באיור שלהלן:

אנו יכולים לראות באיור לעיל כי a[mid]=נתונים. לכן, החיפוש הושלם, והאלמנט נמצא בהצלחה.

הבדלים בין חיפוש ליניארי לחיפוש בינארי

להלן ההבדלים בין חיפוש ליניארי לחיפוש בינארי:

תיאור

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

עבודה של שני החיפושים

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

יישום

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

מוּרכָּבוּת

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

אלמנטים ממוינים

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

גִישָׁה

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

מערך נתונים

אנקפסולציה ב-java

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

מְהִירוּת

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

ממדים

ניתן להשתמש בחיפוש לינארי הן במערך יחיד והן במערך רב-ממדי, בעוד שניתן ליישם את החיפוש הבינארי רק במערך החד-ממדי.

יְעִילוּת

חיפוש לינארי פחות יעיל כשאנחנו לוקחים בחשבון את מערכי הנתונים הגדולים. חיפוש בינארי יעיל יותר מהחיפוש הליניארי במקרה של מערכי נתונים גדולים.

בואו נסתכל על ההבדלים בצורה טבלה.