הפסקת קפה מס' 156. כיצד להשתמש בשיטת Arrays.binarySearch() ב-Java

מקור: FreeCodeCamp עם מאמר זה, תלמד כיצד להשתמש בשיטת Arrays.binarySearch() ב-Java.

מה זה Arrays.binarySearch() ב-Java?

התיעוד הרשמי עבור שיטת Arrays.binarySearch() קובע:

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

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

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';

		int foundItemIndex = Arrays.binarySearch(vowels, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

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

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

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

מה קורה כאשר Arrays.binarySearch() לא מוצא אלמנט נתון?

בואו נסתכל שוב על התיעוד הרשמי עבור שיטת Arrays.binarySearch() :

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

לא ממש ברור, נכון? השורה הראשונה מציינת שהשיטה תחזיר את האינדקס של המפתח מהחיפוש אם הוא נמצא במערך. אם הוא לא נמצא, הפלט יהיה שווה לערך (-(נקודת הכנסה) - 1) . בהתאם למפתח החיפוש, לנקודת ההכנסה יכולות להיות משמעויות שונות. נניח שיש לנו מערך [5, 6, 7, 8, 9, 10] ומפתח חיפוש של 0 , שברור שלא נמצא במערך. במקרה זה, מפתח החיפוש קטן מכל רכיבי המערך. אבל האלמנט הראשון שגדול ממפתח החיפוש הוא 5 . לפיכך, במקרה שלנו נקודת ההכנסה תהיה: אתה יכול ליישם את זה בקטע קוד כמו זה:

package arrays;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 0)); // -1
	}
}

נניח שוב שיש לנו מערך [5, 6, 7, 8, 9, 10] ומפתח חיפוש של 12 , שברור שלא נמצא במערך. במקרה זה, מפתח החיפוש גדול מכל רכיבי המערך. כאן נקודת ההכנסה תהיה כזו: זכור שאם אינך מציין ידנית את אינדקס הסיום, השיטה משתמשת באורך המערך כאינדקס הסיום, שבמקרה זה הוא 6 . אתה יכול ליישם את זה בקטע קוד כמו זה:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 12)); // -7
	}
}

עם זאת, התוצאות ישתנו אם תגדיר את אינדקס ההתחלה והסיום באופן ידני:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		int startIndex = 1;
		int endIndex = 3;

		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2
		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4

	}
}

נסה לחשב את הערכים בעצמך. אתה יכול גם להשתמש בשיטת Arrays.binarySearch() עם סמלים כמו זה:

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key));

	}
}

אותם עקרונות חלים אם מפתח החיפוש שצוין לא נמצא. אך כאשר משווים בין תו במערך לבין מפתח חיפוש נתון, ישמש קוד ASCII של התו המתאים. כלומר, A (65) יהיה פחות מ- (97) . קח זאת בחשבון בעת ​​בדיקת הצלבה של הפלט של התוכנית שלך.