חיפוש בינארי ב-Java: אוספים רקורסיביים, איטרטיביים ו-Java

חיפוש לינארי ב-Java תמיד היה שיטת הבחירה למציאת אלמנט במערך. הוא מחפש כל רכיב של המערך ברצף וקל מאוד ליישום. עם זאת, החסרונות של החיפוש הליניארי ברורים כאשר המערך המדובר מכיל עשרות אלפי אלמנטים. במקרים כאלה, שיטת "הפרד וכבוש" המיושמת על ידי חיפוש בינארי היא הרבה יותר יעילה ועדיפה עבור מתכנתים עם מחשבה על מורכבות זמן ומרחב.

חיפוש בינארי

בחיפוש בינארי, מערך מחולק שוב ושוב לשני חצאים עד למציאת המפתח (האלמנט שמחפשים). החלוקה היא וירטואלית כלומר, שלמות הנתונים נשמרת. בכל איטרציה, הערך האמצעי של המערך ממוקד. אם הערך שווה למפתח שאנו מחפשים, הלולאה או הפונקציה הרקורסיבית מסתיימת. אחרת, זה ממשיך להסתובב. אם הערך האמצעי גדול מהמפתח, הפונקציה מתמקדת בחצי הראשון של המערך ולהיפך. תהליך זה חוזר על עצמו עד שהמפתח נמצא או שהמערך כולו עבר איטרציה.

ההבדל בין חיפוש ליניארי לבינארי

אלגוריתם חיפוש בינארי

האלגוריתם של החיפוש הבינארי ניתן להלן.

1. קבע את הנקודות הראשונות והאחרונות של המערך. הנקודות יותאמו בכל איטרציה לפי המערך והמפתח שמחפשים.
2. חזור על המערך והשווה את הערך האמצעי בין הנקודה הראשונה והאחרונה הנוכחית שלך. באיטרציה הראשונה, המשתנה הראשון והאחרון יהיו זהים לאלו בפועל במערך.
3. אם המפתח גדול מהערך האמצעי, האינדקס של ערך זה יאוחסן במשתנה "הראשון" החדש.
4. אם המפתח קטן מהערך האמצעי, האינדקס של ערך זה יאוחסן במשתנה 'אחרון'.
5. מצב זה חוזר על עצמו עד שאחד משני התנאים מתגשם:
   • מפתח נמצא.
   • המערך כולו עבר איטרציה.

הקוד לחיפוש בינארי איטרטיבי וגם לחיפוש בינארי רקורסיבי ניתן להלן.

חיפוש בינארי איטרטיבי

הקוד לחיפוש בינארי בשיטה איטרטיבית ניתן להלן.

import java.util.Scanner;
public class IterativeBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
       
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
       
        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);
       
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;
 
        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

חיפוש בינארי רקורסיבי

הקוד עבור בינארי באמצעות רקורסיה ניתן להלן.

import java.util.Scanner;
public class RecursiveBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
 
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
 
        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);
 
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;
 
       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;
 
       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);
 
       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }
 
}

מורכבות זמן

עם כל איטרציה שעוברת, המערך כלומר מרחב החיפוש מחולק לחצי. לאחר כל איטרציה 'm', חלל החיפוש ישתנה לגודל של N/2m. בתרחיש הגרוע ביותר, נישאר רק עם אלמנט אחד בצד אחד המרוחק של המערך. בשלב זה, המורכבות של החיפוש הבינארי תהיה k = log2N. מורכבות הזמן של חיפוש לינארי היא O(N) מה שמביא לכך שהחיפוש הבינארי מהיר הרבה יותר עם המורכבות O(log2N). זהו היתרון העיקרי של שימוש בחיפוש בינארי על פני חיפוש ליניארי.

מורכבות החלל

חיפוש בינארי משתמש בשלושה משתנים שונים - התחלה, סוף ואמצע. שלושת המשתנים הללו נוצרים כמצביעים המצביעים על מיקום הזיכרון של מדדי המערך. בשל כך, החיפוש הבינארי יעיל ביותר עם שטח. מורכבות החלל של חיפוש בינארי איטרטיבי היא O(1). עבור יישום רקורסיבי, זה O(log N).