07-08-2005, 23:46
|
|
|
|
חבר מתאריך: 20.06.03
הודעות: 5,616
|
|
חיפוש בינארי
שיטת חיפוש בנתונים ממויינים, לדוגמה מערך.
השיטה מתבססת על חלוקת הנתונים ל-2 כל פעם (ומכאן בינארי).
לדוגמה:
נתון מערך בעל n איברים ממויינים.
אנו מחפשים את האיבר בעל הערך a.- נבחן את הערך של האיבר ה-n/2.
- אם ערך האיבר גדול מ-a נבצע שוב את התהליך על תת המערך שאיבריו 0 עד n/2
- עם ערך האיבר קטן מ-a נבצע שוב את התהליך על תת המערך שאיבריו n/2 עד n
- עם ערך האיבר שווה ל-a החזר אותו.
אם ניקח מערך בן 100 מספרים ממויינים ואנו מחפשים את מיקומו של האיבר השווה ל-2250.
נבדוק את איבר 50, אם ערכו קטן מ 2250, נתחיל שוב את הפעולה כשעכשיו יש לנו מערך קטן
יותר בן 50 איברים (במקור היה מספרם 51 - 100, עכשיו זהו מערך חדש בן 50 איברים מ-0 עד 50) וחוזר חלילה עד למציאת האיבר שלנו.
|