תוֹכֶן

• טבלת השוואה
• הגדרה של חיפוש לינארי
• הגדרה של חיפוש בינארי
• סיכום

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

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

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

1. טבלת השוואה
2. הגדרה
3. הבדלים עיקריים
4. סיכום

טבלת השוואה

בסיס להשוואה	חיפוש לינארי	חיפוש בינארי
מורכבות זמן	O (N)	O (יומן 2 N)
זמן המקרה הטוב ביותר	אלמנט ראשון O (1)	מרכיב מרכזי O (1)
תנאי מוקדם למערך	לא נדרש	המערך חייב להיות בסדר ממוין
המקרה הגרוע ביותר עבור מספר N של אלמנטים	יש צורך בהשוואות	יכול לסיים אחרי יומן בלבד2השוואות N
ניתן ליישום ב-	מערך ורשימה מקושרת	לא ניתן ליישם ישירות ברשימה המקושרת
הכנס פעולה	מוכנס בקלות בסוף הרשימה	דרוש עיבוד כדי להכניס אותו למקום הראוי לשמירה על רשימה ממוינת.
סוג האלגוריתם	איטרטיבי באופיו	להתחלק ולכבוש בטבע
שימושיות	קל לשימוש וללא צורך באלמנטים מסודרים.	בכל מקרה אלגוריתם ואלמנטים מסובכים צריכים להיות מסודרים לפי הסדר.
שורות קוד	פחות	יותר

הגדרה של חיפוש לינארי

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

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

יעילות של חיפוש לינארי

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

תוכנית C לחפש אלמנט עם טכניקת חיפוש לינארית.

# כלול # כלול void main () {int a, n, i, item, loc = -1; clrscr (); f (" n הזן את מספר האלמנטים:"); scanf ("% d", & n); f ("הזן את המספרים: n"); עבור (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" n הזן את המספר לחיפוש:"); scanf ("% d", & פריט); עבור (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; לשבור; }} if (loc> = 0) {f (" n% d נמצא במיקום% d:", פריט, loc + 1); } else {f (" n הפריט לא קיים"); } גץ '(); }

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

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

ההיגיון מאחורי טכניקה זו ניתן להלן:

• ראשית, מצא את האלמנט האמצעי במערך.
• האלמנט האמצעי של המערך מושווה לאלמנט אותו יש לחפש.

ישנם שלושה מקרים שעלולים להיווצר:

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

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

תוכנית C למצוא אלמנט עם טכניקת חיפוש בינארית.

# כלול void main () {int i, beg, end, middle, n, search, array; f ("הזן את מספר האלמנט n"); scanf ("% d", & n); f ("הזן את המספרים% d n", n); עבור (i = 0; i <n; i ++) scanf ("% d", & array); f ("הזן את המספר לחיפוש n"); scanf ("% d", וחיפוש); מתחנן = 0; סוף = n - 1; אמצע = (התחלה + סוף) / 2; בזמן (התחלה <= סוף) {if (מערך <חיפוש) התחל = אמצע + 1; אחרת אם (מערך == חיפוש) {f ("החיפוש מצליח. n% d נמצא במיקום% d. n", חיפוש, אמצע + 1); לשבור; } סוף אחר = אמצע - 1; אמצע = (התחלה + סוף) / 2; } if (beg> end) f ("החיפוש לא הצליח!% d אינו קיים ברשימה. n", חיפוש); גץ '(); }

1. חיפוש לינארי הוא איטרטיבי באופיו ומשתמש בגישה רציפה. מצד שני, חיפוש בינארי מיישם גישה ומכבש גישה.
2. מורכבות הזמן של חיפוש לינארי היא O (N) ואילו לחיפוש בינארי יש O (log₂נ).
3. זמן המקרים הטוב ביותר בחיפוש לינארי הוא עבור האלמנט הראשון, כלומר O (1). לעומת זאת, בחיפוש בינארי זה מיועד לאלמנט האמצעי, כלומר O (1).
4. בחיפוש הקווי, המקרה הגרוע ביותר לחיפוש אלמנט הוא מספר N של השוואה. לעומת זאת, זה יומן₂מספר N של השוואה לחיפוש בינארי.
5. ניתן ליישם חיפוש לינארי במערך כמו גם ברשימה מקושרת ואילו לא ניתן ליישם חיפוש בינארי ישירות ברשימה המקושרת.
6. כידוע חיפוש בינארי מחייב את המערך הממוין וזו הסיבה שהוא דורש עיבוד להכניס למקום הראוי שלו כדי לשמור על רשימה ממוינת. נהפוך הוא, חיפוש לינארי אינו מצריך אלמנטים ממוינים, ולכן אלמנטים מוכנסים בקלות בסוף הרשימה.
7. חיפוש לינארי קל לשימוש, ואין צורך באלמנטים מסודרים. מצד שני, אלגוריתם החיפוש הבינארי הוא מסובך ככל שיהיה, ואלמנטים מסודרים בהכרח לפי סדר.

סיכום

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

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