Trong ví dụ này, chúng ta sẽ học cách triển khai thuật toán tìm kiếm nhị phân trong Java.
Để hiểu ví dụ này, bạn nên có kiến thức về các chủ đề lập trình Java sau:
- Java while và do… while Loop
- Câu lệnh Java if… else
- Mảng Java
Ví dụ: Chương trình Java để triển khai thuật toán tìm kiếm nhị phân
import java.util.Scanner; // Binary Search in Java class Main ( int binarySearch(int array(), int element, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( // get index of mid element int mid = low + (high - low) / 2; // if element to be searched is the mid element if (array(mid) == element) return mid; // if element is less than mid element // search only the left side of mid if (array(mid) < element) low = mid + 1; // if element is greater than mid element // search only the right side of mid else high = mid - 1; ) return -1; ) public static void main(String args()) ( // create an object of Main class Main obj = new Main(); // create a sorted array int() array = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; // get input from user for element to be searched Scanner input = new Scanner(System.in); System.out.println("Enter element to be searched:"); // element to be searched int element = input.nextInt(); input.close(); // call the binary search method // pass arguments: array, element, index of first and last element int result = obj.binarySearch(array, element, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
Đầu ra 1
Nhập phần tử cần tìm: 6 Phần tử được tìm thấy ở chỉ mục 3
Ở đây, chúng tôi đã sử dụng Java Scanner Class để lấy đầu vào từ người dùng. Dựa trên đầu vào từ người dùng, chúng tôi sử dụng tìm kiếm nhị phân để kiểm tra xem phần tử có trong mảng hay không.
Chúng ta cũng có thể sử dụng lời gọi đệ quy để thực hiện tác vụ tương tự.
int binarySearch(int array(), int element, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // check if mid element is searched element if (array(mid) == element) return mid; // Search the left half of mid if (array(mid)> element) return binarySearch(array, element, low, mid - 1); // Search the right half of mid return binarySearch(array, element, mid + 1, high); ) return -1; )
Ở đây, phương thức binarySearch()đang gọi chính nó cho đến khi phần tử được tìm thấy hoặc, ifđiều kiện không thành công.
Nếu bạn muốn tìm hiểu thêm về thuật toán tìm kiếm nhị phân, hãy truy cập Thuật toán tìm kiếm nhị phân.
