אלגוריתם חיפוש בינארי בג'אווה
1. סקירה כללית
במאמר זה נסקור את היתרונות של חיפוש בינארי על פני חיפוש לינארי פשוט ונעבור על יישומו ב- Java.
2. צורך בחיפוש יעיל
נניח שאנחנו בעסקי מכירת יין ומיליוני קונים מבקרים ביישום שלנו מדי יום.
באמצעות האפליקציה שלנו, לקוח יכול לסנן פריטים שמחירם נמוך בהמשך נ דולר, בחר בקבוק מתוצאות החיפוש והוסף אותם לעגלת הקניות שלו. יש לנו מיליוני משתמשים המחפשים יינות עם מגבלת מחירים בכל שנייה. התוצאות צריכות להיות מהירות.
בחלק האחורי, האלגוריתם שלנו מבצע חיפוש ליניארי בכל רשימת היינות המשווה את מגבלת המחירים שהזמין הלקוח עם המחיר של כל בקבוק יין ברשימה.
לאחר מכן הוא מחזיר פריטים שמחירם נמוך או שווה למגבלת המחיר. לחיפוש לינארי זה מורכבות זמן של עַל).
פירוש הדבר שככל שמספר גדול יותר של בקבוקי היין במערכת שלנו, כך ייקח יותר זמן. זמן החיפוש גדל באופן יחסי למספר הפריטים החדשים שהוצגו.
אם נתחיל לשמור פריטים בסדר ממוין ונחפש פריטים באמצעות החיפוש הבינארי, נוכל להשיג מורכבות של O (יומן n).
בחיפוש בינארי, הזמן שלוקח תוצאות החיפוש גדל באופן טבעי עם גודל מערך הנתונים, אך לא באופן פרופורציונלי.
3. חיפוש בינארי
במילים פשוטות, האלגוריתם משווה בין מַפְתֵחַ ערך עם האלמנט האמצעי של המערך; אם הם לא שווים, המחצית בה המפתח לא יכול להיות חלק מתבטל, והחיפוש נמשך אחר המחצית הנותרת עד שהוא יצליח.
זכרו - ההיבט המרכזי כאן הוא שהמערך כבר ממוין.
אם החיפוש מסתיים כשהחצי הנותר ריק מַפְתֵחַ לא נמצא במערך.
3.1. Implative Impl
public int runBinarySearchIteratively (int [] sortedArray, int key, int low, int high) {int index = Integer.MAX_VALUE; ואילו (נמוך <= גבוה) {int mid = (low + high) / 2; אם (sortedArray [mid] key) {high = mid - 1; } אחרת אם (sortedArray [mid] == key) {index = mid; לשבור; }} אינדקס החזר; }ה runBinarySearch באופן יחסי השיטה לוקחת א sortedArray, מַפְתֵחַ & ה נָמוּך & גָבוֹהַ אינדקסים של sortedArray כטיעונים. כאשר השיטה פועלת בפעם הראשונה ה- נָמוּך, המדד הראשון של sortedArray, הוא 0, ואילו ה- גָבוֹהַ, המדד האחרון של sortedArray, שווה לאורכו - 1.
ה אֶמצַע הוא האינדקס האמצעי של sortedArray. כעת האלגוריתם מריץ א בזמן לולאה המשווה את מַפְתֵחַ עם ערך המערך של האינדקס האמצעי של sortedArray.
3.2. Impl רקורסיבית
עכשיו, בואו נסתכל גם על יישום פשוט, רקורסיבי:
public int runBinarySearchRecursively (int [] sortedArray, int key, int low, int high) {int middle = (low + high) / 2; אם (גבוה <נמוך) {החזר -1; } אם (key == sortedArray [middle]) {return middle; } אחר אם (מקש <sortedArray [middle]) {return runBinarySearchRecursively (sortedArray, key, low, middle - 1); } אחר {להחזיר runBinarySearchRecursively (sortedArray, key, middle + 1, high); }} ה runBinarySearchRecursively השיטה מקבלת א sortedArray, מַפְתֵחַ, ה נָמוּך ו גָבוֹהַ אינדקסים של sortedArray.
3.3. באמצעות מערכים.חיפוש בינארי()
אינדקס int = Arrays.binarySearch (sortedArray, key); מערך ממוין ו intמַפְתֵחַ, שיש לחפש במערך המספרים השלמים, מועברים כארגומנטים ל- חיפוש בינארי שיטת ה- Java מערכים מעמד.
3.4. באמצעות אוספים.חיפוש בינארי()
אינדקס int = Collections.binarySearch (sortedList, key); רשימת מיונים ו מספר שלםמַפְתֵחַ, שיש לחפש ברשימת מספר שלם אובייקטים, מועברים כטיעונים ל חיפוש בינארי שיטת Java אוספים מעמד.
3.5. ביצועים
אם להשתמש בגישה רקורסיבית או איטרטיבית לכתיבת האלגוריתם זה בעיקר עניין של העדפה אישית. אך עדיין הנה כמה נקודות שעלינו להיות מודעים להן:
1. רקורסיה יכולה להיות איטית יותר בגלל התקורה של שמירה על א לַעֲרוֹם ובדרך כלל תופס יותר זיכרון
2. רקורסיה אינה לַעֲרוֹם-יְדִידוּתִי. זה עלול לגרום StackOverflowException בעת עיבוד ערכות נתונים גדולות
3. רקורסיה מוסיפה לקוד בהירות מכיוון שהיא מקצרת אותו בהשוואה לגישה האיטרטיבית
באופן אידיאלי, חיפוש בינארי יבצע פחות השוואות בניגוד לחיפוש לינארי לערכים גדולים של n. לערכים קטנים יותר של n, החיפוש הליניארי יכול לבצע ביצועים טובים יותר מחיפוש בינארי.
צריך לדעת כי ניתוח זה הוא תיאורטי ועשוי להשתנות בהתאם להקשר.
גַם, אלגוריתם החיפוש הבינארי זקוק למערכת נתונים ממוינת שיש לה גם עלויות. אם אנו משתמשים באלגוריתם למיזוג למיון הנתונים, מורכבות נוספת של n יומן n נוסף לקוד שלנו.
אז ראשית עלינו לנתח היטב את הדרישות שלנו ואז לקבל החלטה באיזה אלגוריתם חיפוש יתאים לדרישות שלנו בצורה הטובה ביותר.
4. מסקנה
הדרכה זו הדגימה יישום אלגוריתם חיפוש בינארי ותרחיש בו יהיה עדיף להשתמש בו במקום חיפוש לינארי.
אנא מצא את הקוד להדרכה ב- GitHub.
