חיפוש: ליניארי ובין-מונדי
עמוד זה דורש דפדפן עדכני (תומך ב-SharedArrayBuffer). אנא עדכן את Chrome, Edge, Firefox או Safari לגרסה העדכנית ביותר.
מציאת ערך
- משימה נפוצה היא חיפוש: האם ערך קיים במערך, ואם כן, איפה?
- התשובה המקובלת היא המדד שבו נמצא, או
-1אם אינו קיים. - לומדים שתי דרכים: חיפוש ליניארי (עובד בכל מערך) וחיפוש בינארי (דורש מערך מוצע, אך מהיר משמעותית).
חיפוש ליניארי
- סוקר כל פריט מהמדד
0ועד הסוף. - אם הפריט שווה למטרה, חזר את המדד שלו מיידית.
- אם הלופס הסתיים ללא התאמה, חזור
-1.
English
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
כמה מהיר חיפוש ליניארי?
- במקרה הגרוע (הערך נמצא באחרון, או שאינו קיים) הוא בודק כל פריט.
- לרשימה של
nפריטים זה עשוי להגיע עדnבדיקות. מכנים זאת זמן ליניארי. - למערכים קטנים זה מושלם לחלוטין. עבור מערכים גדולים מאוד מוצעים ניתן לעשות טוב יותר.
חיפוש בינארי דורש מערך מסודר
- חיפוש בינארי פועל רק כאשר המערך כבר מסודר (מקטן לגדול).
- הוא בודק את הפריט ב-אמצע, ואז מוותר על חצי מהמערך בכל שלב.
- זה הרבה יותר מהיר: מיליון פריטים לוקחים כ-20 בדיקות, ולא מיליון.
רעיון חיפוש בינארי
- שמור שני גבולות:
low(התחלה) ו-high(סוף). - תבדוק את המדד האמצעי
mid = (low + high) / 2. - אם
a[mid]שווה למטרה, חזורmid. - אם
a[mid]שווה למטרה, החזרlow = mid + 1. - אם
a[mid]קטן מדי, המטרה חייבת להיות בימין, אז הגדר מחדש אתhigh = mid - 1. - עצור כאשר
lowעובר אתhigh; אז הערך אינו קיים, חזור-1.
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
כאשר ערך חסר
- שתי החיפושים מחזירות
-1כאשר המטרה אינה נמצאת במערך. - בחיפוש בינארי, הלולאה מסתיימת כאשר
low > high— הגבולות חצו זה את זה, ולכן אין מקום נוסף לחפש. - שתי שיטות החיפוש מחזירות
-1כאשר המטרה אינה במערך.
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
טעויות נפוצות
- חיפוש בינארי דורש מערך מסודר.
- חיפוש ליניארי הוא O(n); בינארי הוא O(log n).
כעת תנסו בעצמכם
- כל משימה ממלאת מראש את שלד המחלקה — כתוב את הקוד שלך בתוך main, או השלם את השיטה המוצגת.
- השתמשו ב-Check answer כדי לקמפיל את הקוד שלך עם הבדיקות הסופקות ולצפות בתוצאות. שמרו את ממשקי המחלקה והשיטה המוצגים בתחילת העבודה.
- הקוד שלך נרכב ונרץ על השרת, ולכן גם ההפעלה הראשונה היא מהירה.
חקור
חיפוש ליניארי לעומת חיפוש בינארי
חיפוש בין-מונדי חותך את הטווח למחצה בכל צעד — מספר בדיקות מעט יותר פחות.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם linearSearch(int[] a, int target). החזר את המדד של הפריט הראשון השווה לtarget, או -1 אם הוא אינו קיים במטריצה. בדוק פריטים החל מהמדד 0 ומעלה.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם binarySearch(int[] a, int target) עבור מערך מועלה. השתמש בגבולות low/high ובדוק את האמצע בכל צעד. החזר את המקדם של target, או -1 אם הוא אינו קיים.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
השלם countOccurrences(int[] a, int target) שמחזיר כמה פעמים הtarget מופיע בa (סריקה ליניארית). החזר 0 אם לעולם לא מופיע.
לחץ על הרץ כדי לראות את התוצא כאן.