יישום איטרטיבי של אלגוריתם החיפוש הבינארי הפופולרי למציאת אלמנט במערך ממוין.
שלום לכולם! פרסמתי בבלוג שלי הרבה אלגוריתמים ומאמרי מבנה נתונים, אבל זה הראשון כאן. במאמר זה נבחן אלגוריתמים בסיסיים פופולריים לראיונות.
כן, ניחשתם נכון: עליכם ליישם חיפוש בינארי בג'אווה, ועליכם לכתוב גם אלגוריתמי חיפוש בינאריים איטרטיביים וגם רקורסיביים.
במדעי המחשב, חיפוש בינארי, או חיפוש חצי מרווח, הוא אלגוריתם חלוקה וכיבוש שמאתר את המיקום של פריט במערך ממוין. חיפוש בינארי עובד על ידי השוואת ערך קלט לאלמנט האמצעי של המערך.
ההשוואה קובעת אם האלמנט שווה לקלט, הוא פחות מהקלט או גדול מהקלט.
כאשר האלמנט המושווה שווה לקלט, החיפוש נעצר ומחזיר בדרך כלל את מיקום האלמנט.
אם האלמנט אינו שווה לקלט, אז מתבצעת השוואה כדי לקבוע אם הקלט קטן או גדול מהאלמנט.
בהתאם לתוצאה, האלגוריתם מתחיל מחדש, אך רק מחפש בחלק העליון או בתחתית התחתונה של רכיבי המערך.
אם הקלט אינו ממוקם בתוך המערך, האלגוריתם בדרך כלל יפיק ערך ייחודי המציין זאת כמו -1 או פשוט יזרוק RuntimeException בג'אווה כמו NoValueFoundException.
אלגוריתמי חיפוש בינארי בדרך כלל מחצי את מספר הפריטים שיש לבדוק עם כל איטרציה עוקבת, וכך מאתרים את הפריט הנתון (או קובעים את היעדרו) בזמן לוגריתמי.
אם לא ידוע לך על אלגוריתמי חיפוש ומיון בסיסיים, תוכל להצטרף לקורס כמו מבני נתונים ואלגוריתמים: Deep Dive באמצעות Java כדי ללמוד אלגוריתמים בסיסיים.
אם ג'אווה אינה בחירת השפה שלך, תוכל למצוא המלצות נוספות עבור JavaScript ו- Python ברשימה זו של קורסים באלגוריתמים.
ללא שם: אם אתה מעדיף ספרים, אני ממליץ לך לקרוא ספר אלגוריתמים מקיף כמו מבוא לאלגוריתמים מאת תומאס ה 'קורמן.
להלן מספר דוגמאות המציג את ההיגיון של חיפוש בינארי איטרטיבי ב- Java :
יישום חיפוש בינארי בג'אווה
הנה תוכנית לדוגמא ליישום חיפוש בינארי בג'אווה. האלגוריתם מיושם רקורסיבית. כמו כן, עובדה מעניינת לדעת על יישום חיפוש בינארי בג'אווה היא שג'ושוע בלוך, מחבר ספר ה- Java היעיל המפורסם, כתב את החיפוש הבינארי ב "java.util.Arrays".
import java.util.Arrays;import java.util.Scanner;/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/public class IterativeBinarySearch { public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list)); binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list)); binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list)); binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333); // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list); // Search an element int index = Arrays.binarySearch(list, 3);}/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}middle = (first + last) / 2;}if (first > last) { System.out.println(number + " is not present in the list.\n");}}}OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.זה הכל על איך ליישם חיפוש בינארי באמצעות רקורסיה ב- Java . יחד עם חיפוש לינארי, אלה שניים מאלגוריתמי החיפוש החיוניים שאתה לומד בשיעור מדעי המחשב שלך.
מבנה נתוני עץ החיפוש הבינארי מנצל את האלגוריתם הזה ומסדר נתונים במבנה היררכי כך שתוכלו לחפש בכל צומת בזמן O (logN).
עם זאת, עליכם לזכור שכדי להשתמש בחיפוש בינארי, עליכם לרשימה או מערך ממוינים, לכן עליכם לשקול גם את עלות המיון כאשר אתם שוקלים להשתמש באלגוריתם חיפוש בינארי בעולם האמיתי.
למידה נוספת
מבני נתונים ואלגוריתמים: צלילה עמוקה באמצעות Java
אלגוריתמים ומבני נתונים - חלק 1 ו -2
מבני נתונים בג'אווה 9 מאת היינץ קבוץ
10 ספרי אלגוריתמים לראיונות
10 קורסים למבנה נתונים ואלגוריתם לראיונות
5 קורסים בחינם ללימוד מבנה נתונים ואלגוריתמים
מדריכי מבנה נתונים אחרים ואלגוריתמים שעשויים למצוא חן בעיניכם
- כיצד ליישם אלגוריתם Quicksort במקום ב- Java? (הדרכה)
- כיצד ליישם עץ חיפוש בינארי ב- Java? (פִּתָרוֹן)
- כיצד ליישם אלגוריתם Quicksort ללא רקורסיה? (הדרכה)
- כיצד ליישם אלגוריתם מיון הכנסה ב- Java? (הדרכה)
- How to implement Bubble sort algorithm in Java? (tutorial)
- What is the difference between Comparison and Non-Comparison based sorting algorithm? (answer)
- How to implement Bucket Sort in Java? (tutorial)
- How to implement a Binary Search Algorithm without recursion in Java? (tutorial)
- 50+ Data Structure and Algorithms Courses for Programmers (questions)
Thanks for reading this article. If you like this article then please share with your friends and colleagues. If you have any suggestion or feedback then please drop a comment.