חיפוש לינארי ב-Java תמיד היה שיטת הבחירה למציאת אלמנט במערך. הוא מחפש כל רכיב של המערך ברצף וקל מאוד ליישום. עם זאת, החסרונות של החיפוש הליניארי ברורים כאשר המערך המדובר מכיל עשרות אלפי אלמנטים. במקרים כאלה, שיטת "הפרד וכבוש" המיושמת על ידי חיפוש בינארי היא הרבה יותר יעילה ועדיפה עבור מתכנתים עם מחשבה על מורכבות זמן ומרחב.
חיפוש בינארי
בחיפוש בינארי, מערך מחולק שוב ושוב לשני חצאים עד למציאת המפתח (האלמנט שמחפשים). החלוקה היא וירטואלית כלומר, שלמות הנתונים נשמרת. בכל איטרציה, הערך האמצעי של המערך ממוקד. אם הערך שווה למפתח שאנו מחפשים, הלולאה או הפונקציה הרקורסיבית מסתיימת. אחרת, זה ממשיך להסתובב. אם הערך האמצעי גדול מהמפתח, הפונקציה מתמקדת בחצי הראשון של המערך ולהיפך. תהליך זה חוזר על עצמו עד שהמפתח נמצא או שהמערך כולו עבר איטרציה.
ההבדל בין חיפוש ליניארי לבינארי
חיפוש לינארי |
חיפוש בינארי |
מחפש ברצף במערך |
מחלק את המערך לשני חצאים עד שנמצא הערך |
עובד עם כל מערך |
עובד רק עם מערכים ממוינים |
מורכבות היא O(N) |
המורכבות היא O(log2N) |
יכול לעבוד על מערכים ממוינים ולא ממוינים |
ניתן ליישם רק על מערכים ממוינים. |
פחות מורכב ליישום |
יותר מורכב ליישום |
אלגוריתם חיפוש בינארי
האלגוריתם של החיפוש הבינארי ניתן להלן.
- קבע את הנקודות הראשונות והאחרונות של המערך. הנקודות יותאמו בכל איטרציה לפי המערך והמפתח שמחפשים.
- חזור על המערך והשווה את הערך האמצעי בין הנקודה הראשונה והאחרונה הנוכחית שלך. באיטרציה הראשונה, המשתנה הראשון והאחרון יהיו זהים לאלו בפועל במערך.
- אם המפתח גדול מהערך האמצעי, האינדקס של ערך זה יאוחסן במשתנה "הראשון" החדש.
- אם המפתח קטן מהערך האמצעי, האינדקס של ערך זה יאוחסן במשתנה 'אחרון'.
- מצב זה חוזר על עצמו עד שאחד משני התנאים מתגשם:
- מפתח נמצא.
- המערך כולו עבר איטרציה.
הקוד לחיפוש בינארי איטרטיבי וגם לחיפוש בינארי רקורסיבי ניתן להלן.
חיפוש בינארי איטרטיבי
הקוד לחיפוש בינארי בשיטה איטרטיבית ניתן להלן.
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){
int start = 0;
int end = arr.length;
for(int i = 0; iarr[n]){
start = n;
}
else{
end = n;
}
}
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){
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
if(arr[n]==num)
return n;
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
מורכבות זמן
עם כל איטרציה שעוברת, המערך כלומר מרחב החיפוש מחולק לחצי. לאחר כל איטרציה 'm', חלל החיפוש ישתנה לגודל של N/2m. בתרחיש הגרוע ביותר, נישאר רק עם אלמנט אחד בצד אחד המרוחק של המערך. בשלב זה, המורכבות של החיפוש הבינארי תהיה k = log2N. מורכבות הזמן של חיפוש לינארי היא O(N) מה שמביא לכך שהחיפוש הבינארי מהיר הרבה יותר עם המורכבות O(log2N). זהו היתרון העיקרי של שימוש בחיפוש בינארי על פני חיפוש ליניארי.
מורכבות החלל
חיפוש בינארי משתמש בשלושה משתנים שונים - התחלה, סוף ואמצע. שלושת המשתנים הללו נוצרים כמצביעים המצביעים על מיקום הזיכרון של מדדי המערך. בשל כך, החיפוש הבינארי יעיל ביותר עם שטח. מורכבות החלל של חיפוש בינארי איטרטיבי היא O(1). עבור יישום רקורסיבי, זה O(log N).
GO TO FULL VERSION