שיעור 5: מערכים ושני מצביעים

חשבו על מדף ספרים צמודים בשורה: רוצים את השלישי? סופרים שלושה וקופצים ישר אליו. זה מערך (array) — הגעה לפריט לפי אינדקס היא O(1). היום נכיר טריק נחמד, 'שני מצביעים' (two pointers): במקום סמן אחד שעובר על הכול, מפעילים שניים שזזים זה לקראת זה — וכך פותרים בעיות רבות במעבר יחיד, O(n), במקום O(n²).

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

שני מצביעים: דפוס שבו שני אינדקסים נעים על מערך (מהקצוות פנימה או באותו כיוון) כדי לפתור בעיה במעבר יחיד.
במקום (in-place): שינוי הנתונים בתוך המבנה הקיים בלי להקצות מבנה חדש — O(1) זיכרון נוסף.
זיכרון רציף: אחסון איברים זה לצד זה בזיכרון, מה שמאפשר גישה לפי אינדקס ב-O(1) וסריקה ידידותית ל-cache.