חיפוש: ליניארי ובין-מונדי
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
שתי דרכים לחיפוש
- חיפוש פירונו למצוא היכן נמצא ערך במערך (או לומר שהוא אינו קיים).
- חיפוש ליניארי בודק כל פריט אחד אחר אחד. הוא עובד על כל מערך.
- חיפוש בינארי מהיר הרבה יותר אך דורש שהמערך יהיה מוסדר קודם לכן.
חיפוש ליניארי
- הליך מהאינדקס
0עדn - 1, והשווה כל פריט למטרה. - מחזירים את האינדקס ברגע שמצאים אותו. אם מגיעים לסוף, מחזירים
-1. - עבור מערך של
nפריטים, זה בודק עדnמהם.
מדמה מיון מאפשר חיפוש בינארי
- אם המערך מונה, ניתן לקפוץ לאמצע ולהשוות.
- אם האמצע קטן מדי, היעד חייב להיות בחצי הימני; אם גדול מדי, בחצי השמאלי.
- בכל צעד נזרק חצי מהמערך, ולכן זה מאוד מהיר (כ-
log2(n)צעדים).
low, high, mid
- שמור שתי גבולות:
low(התחלה) וhigh(סוף). האמצע הואmid = low + (high - low) / 2. - אם
a[mid]הוא היעד, החזרmid. אםa[mid] < target, הזזlow = mid + 1; אחרתhigh = mid - 1. - עצור כשהיחס
low > high— היעד אינו קיים, לכן החזר-1.
English
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
טעויות נפוצות
- חיפוש בינארי דורש מערך מסודר.
- חיפוש ליני בודק כל אלמנט בסדר.
כעת תנסו בעצמכם
- לחיפוש בינארי, הנח שהמערך כבר מוה. השתמש ב
low,high, ובmid. - החזר
-1כאשר הערך לא נמצא. אל תכתובmain— הבוקר מספק אותו.
חקור
חיפוש ליניארי לעומת חיפוש בינארי
חיפוש בינארי מחלק את הטווח לשני חלקים בשלבים.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int linear_search(const int a[], int n, int target) כך שתחזיר את האינדקס של ה-target הראשון, או -1 אם הוא אינו קיים במערך. אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int binary_search(const int a[], int n, int target) למערך מוגדר. החזר את האינדקס של target, או -1. השתמש ב-low, high ו-mid. אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם int first_negative(const int a[], int n) כך שתחזיר את האינדקס של הפריט הקטן ביותר מה-0, או -1 אם אין כזה. אל תכתב פונקציה main.
לחץ על הרץ כדי לראות את התוצא כאן.