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

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

לשיטה האיטרטיבית יש מורכבות שטח של O(1) לעומת O(לוגן) מיוצר בשיטה רקורסיבית. אז איך אתה יכול ליישם את אלגוריתם החיפוש הבינארי באמצעות השיטה האיטרטיבית ב-C, C++ ו-Python?

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

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

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

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

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

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

חיפוש בינארי באמצעות C

בצע את השלבים הבאים כדי ליישם חיפוש בינארי באמצעות C:

כל קוד המקור של תוכנית החיפוש הבינארי המשתמשת ב-C, C++, Java ו-Python קיים בזה מאגר GitHub.

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

#לִכלוֹל <stdio.h>
intחיפוש בינארי(int arr[], int arr_size, int search_number){
/*... */
}

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

ה נָמוּך ו גָבוֹהַ משתנים מאחסנים את האינדקסים המייצגים את הגבולות של מרחב החיפוש הנוכחי. בֵּינוֹנִי מאחסן את האינדקס באמצע:

int נמוך = 0, גבוה = arr_size - 1, באמצע;

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

בזמן (נמוך <= גבוה) {
/* ממשיך... [1] */
 }
לַחֲזוֹר-1;

לאחר עדכון נקודת האמצע בתחילת הלולאה, ישנן שלוש תוצאות אפשריות:

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

/* [1] ...המשך */
 mid = (נמוך + (גבוה - נמוך)) / 2;
if (arr[mid] == search_number)
לַחֲזוֹר בֵּינוֹנִי;
אַחֵראם (arr[mid] > search_number)
 גבוה = אמצע - 1;
אַחֵר
 נמוך = אמצע + 1;

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

intרָאשִׁי(){
int arr[100], i, arr_size, search_number;
 printf("הזן מספר אלמנטים: ");
 scanf("%d", &arr_size);
 printf("נא להזין מספרים: ");
עבור (i = 0; אני < arr_size; i++) {
 scanf("%d", &arr[i]);
 }
printf("הזן מספר לחיפוש: ");
 scanf("%d", &search_number);
i = binarySearch (arr, arr_size, search_number);
אם (i==-1)
 printf("מספר לא קיים");
אַחֵר
 printf("המספר קיים בעמדה %d", i + 1);
לַחֲזוֹר0;
}

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

חיפוש בינארי באמצעות C++

אתה יכול להמיר את תוכנית C לתוכנית C++ על ידי ייבוא ​​ה זרם פלט קלט ו השתמש במרחב שמות std כדי להימנע מלחזור עליו מספר פעמים במהלך התוכנית.

#לִכלוֹל <iostream>
באמצעות מרחב שמותסטד;

להשתמש cout עם מפעיל חילוץ << במקום printf() ו cin עם אופרטור הכנסה >> במקום scanf() ותוכנית C++ שלך מוכנה.

printf("הזן מספר אלמנטים: ");
cout <<"הזן מספר אלמנטים: ";
scanf("%d", &arr_size);
cin >> arr_size;

חיפוש בינארי באמצעות Python

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

defחיפוש בינארי(arr, arr_size, search_number):
 נמוך = 0
 high = arr_size - 1
בזמן נמוך <= גבוה:
 אמצע = נמוך + (גבוה-נמוך)//2
 if arr[mid] == search_number:
לַחֲזוֹר בֵּינוֹנִי
אליף arr[mid] > search_number:
 גבוה = אמצע - 1
אַחֵר:
 נמוך = אמצע + 1
לַחֲזוֹר-1

אתחול שני משתנים, נָמוּך ו גָבוֹהַ, לשמש כגבול התחתון והעליון של הרשימה. בדומה למימוש C, השתמש ב- a בזמן לולאה שמצמצמת את מרחב החיפוש. לְאַתחֵל בֵּינוֹנִי כדי לאחסן את הערך האמצעי של הרשימה. Python מספק את אופרטור חלוקת הקומה (//) המספק את המספר השלם הגדול ביותר האפשרי.

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

arr_size = int (input("הזן מספר אלמנטים: "))
arr=[]
הדפס("נא להזין מספרים: ", סוף="")
עבור i בטווח (0,arr_size):
 arr.append(int(קֶלֶט()))
search_number = int (קלט("הזן מספר לחיפוש: "))
result = binarySearch (arr, arr_size, search_number)
אם תוצאה == -1:
 הדפס("מספר לא קיים")
אַחֵר:
 print("מספר הוא נוכח בעמדה ", (תוצאה + 1))

בדוק את הפונקציה עם קלט משתמש. להשתמש קֶלֶט() כדי לקבל את גודל הרשימה, התוכן שלה ומספר לחיפוש. להשתמש int() להטיל את קלט המחרוזת המתקבלת על ידי Python כברירת מחדל למספר שלם. כדי להוסיף מספרים לרשימה, השתמש ב- לְצַרֵף() פוּנקצִיָה.

שִׂיחָה חיפוש בינארי() ולהעביר את הטיעונים. אם אתה מוצא את המספר, הצג את המיקום או האינדקס שלו, אחרת הודעה האומרת שהמספר אינו קיים.

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

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

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

למד את מבני הנתונים והאלגוריתמים הבסיסיים

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

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