Nghỉ giải lao #156. Cách sử dụng phương thức Arrays.binarySearch() trong Java

Nguồn: FreeCodeCamp Với bài viết này, bạn sẽ tìm hiểu cách sử dụng phương thức Arrays.binarySearch() trong Java.

Arrays.binarySearch() trong Java là gì?

Tài liệu chính thức cho phương thức Arrays.binarySearch() nêu rõ:

• Phương pháp này tìm kiếm giá trị được chỉ định trong mảng byte được chỉ định bằng thuật toán tìm kiếm nhị phân.
• Mảng phải được sắp xếp (sử dụng phương thức Sort(byte[]) ) trước khi thực hiện lệnh gọi. Nếu nó không được sắp xếp, kết quả sẽ không được xác định.
• Nếu mảng chứa nhiều phần tử với giá trị được chỉ định thì không có gì đảm bảo sẽ tìm thấy phần tử nào.

Nói một cách đơn giản, phương thức Arrays.binarySearch() có thể tìm kiếm một phần tử nhất định trong một mảng đã sắp xếp và trả về chỉ mục của nó nếu tìm thấy.

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);

	}
}

Phương thức Arrays.binarySearch() lấy mảng bạn muốn tìm kiếm làm đối số đầu tiên và khóa bạn đang tìm kiếm làm đối số thứ hai. Đầu ra của chương trình trên sẽ là: Hãy nhớ rằng phương thức trả về chỉ mục của phần tử được tìm thấy chứ không phải chính phần tử đó. Bằng cách này, bạn có thể lưu trữ chỉ mục dưới dạng số nguyên giống như số nguyên được sử dụng trong ví dụ này. Theo mặc định, phương thức này sử dụng chỉ mục đầu tiên của mảng làm điểm bắt đầu tìm kiếm và độ dài của mảng làm điểm kết thúc tìm kiếm. Trong trường hợp này, chỉ mục bắt đầu là 0 và chỉ mục kết thúc là 6. Thay vì sử dụng chỉ mục bắt đầu và kết thúc mặc định, bạn có thể tự xác định chúng. Ví dụ: nếu bạn muốn tìm kiếm từ chỉ mục 2 đến chỉ mục 4, bạn có thể thực hiện như sau:

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);

	}
}

Trong trường hợp này, phương thức Arrays.binarySearch() lấy mảng bạn muốn tìm kiếm làm đối số đầu tiên, chỉ mục bắt đầu làm đối số thứ hai, chỉ mục kết thúc làm đối số thứ ba và khóa làm đối số thứ tư. Miễn là bạn giữ chỉ mục kết thúc trong độ dài của mảng thì phương thức sẽ hoạt động tốt. Nhưng nếu bạn vượt quá nó, bạn sẽ nhận được chỉ mục Mảng nằm ngoài phạm vi ngoại lệ . Nó khá đơn giản phải không? Phương thức trả về chỉ mục của phần tử nếu nó được tìm thấy. Nhưng điều gì sẽ xảy ra nếu nó không tìm thấy phần tử đã cho?

Điều gì xảy ra khi Arrays.binarySearch() không tìm thấy phần tử nhất định?

Chúng ta hãy xem lại tài liệu chính thức về phương thức Arrays.binarySearch() :

• Phương thức này tìm chỉ mục của một khóa trong kết quả tìm kiếm nếu nó được chứa trong mảng trong phạm vi đã chỉ định; nếu không thì chúng ta nhận được (-(điểm chèn) - 1) .
• Điểm chèn được định nghĩa là điểm tại đó một khóa sẽ được chèn vào mảng: chỉ mục của phần tử đầu tiên trong phạm vi lớn hơn khóa hoặc toIndex (chỉ mục cuối) nếu tất cả các phần tử trong phạm vi nhỏ hơn khóa được chỉ định.
• Lưu ý rằng giá trị trả về sẽ chỉ lớn hơn hoặc bằng 0 khi tìm thấy khóa.

Không rõ ràng lắm phải không? Dòng đầu tiên cho biết phương thức sẽ trả về chỉ mục của khóa từ tìm kiếm nếu nó được tìm thấy trong mảng. Nếu không tìm thấy thì đầu ra sẽ bằng giá trị (-(điểm chèn) - 1) . Tùy thuộc vào khóa tìm kiếm, điểm chèn có thể có ý nghĩa khác nhau. Giả sử chúng ta có một mảng [5, 6, 7, 8, 9, 10] và khóa tìm kiếm là 0 , rõ ràng là không có trong mảng. Trong trường hợp này, khóa tìm kiếm nhỏ hơn tất cả các phần tử của mảng. Nhưng phần tử đầu tiên lớn hơn khóa tìm kiếm là 5 . Vì vậy, trong trường hợp của chúng tôi, điểm chèn sẽ là: Bạn có thể triển khai điều này trong một đoạn mã như thế này:

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
	}
}

Giả sử một lần nữa rằng chúng ta có một mảng [5, 6, 7, 8, 9, 10] và khóa tìm kiếm là 12 , rõ ràng là không có trong mảng. Trong trường hợp này, khóa tìm kiếm lớn hơn tất cả các phần tử của mảng. Ở đây điểm chèn sẽ như thế này: Hãy nhớ rằng nếu bạn không chỉ định chỉ mục kết thúc theo cách thủ công thì phương thức sẽ sử dụng độ dài của mảng làm chỉ mục kết thúc, trong trường hợp này là 6 . Bạn có thể triển khai điều này trong một đoạn mã như thế này:

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
	}
}

Tuy nhiên, kết quả sẽ thay đổi nếu bạn xác định chỉ mục bắt đầu và kết thúc theo cách thủ công:

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

	}
}

Hãy cố gắng tự tính toán các giá trị. Bạn cũng có thể sử dụng phương thức Arrays.binarySearch() với các ký hiệu như thế này:

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));

	}
}

Các nguyên tắc tương tự cũng được áp dụng nếu không tìm thấy khóa tìm kiếm đã chỉ định. Nhưng khi so sánh giữa một ký tự trong mảng với một khóa tìm kiếm cho trước thì mã ASCII của ký tự tương ứng sẽ được sử dụng. Tức là A (65) sẽ nhỏ hơn a (97) . Hãy tính đến điều này khi kiểm tra chéo đầu ra của chương trình của bạn.