[Thực hành] Cài đặt thuật toán tìm kiếm nhị phân không sử dụng đệ quy

Mục đích

Luyện tập cài đặt thuật toán tìm kiếm nhị phân.

Mô tả

Cài đặt phương thức binarySearch(int[] list) để tìm kiếm một giá trị trong một mảng được sắp xếp theo trật tự tăng dần

Hướng dẫn nộp bài:

• Up mã nguồn lên github
• Paste link github vào phần nộp bài

Hướng dẫn

Bước 1: Tạo lớp BinarySearch, khai báo một mảng số nguyên được sắp xếp theo thứ tự tăng dần.

public class BinarySearch {
    static int[] list = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
    /* codes below here */ }

Bước 2: Cài đặt phương thức binarySearch(int[] list, int key).

Binary Search tìm kiếm một phần tử cụ thể bằng cách so sánh phần tử tại vị trí giữa nhất của tập dữ liệu. Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Nếu phần tử cần tìm là lớn hơn giá trị phần tử giữa thì phần tử cần tìm được tìm trong mảng con nằm ở bên phải phần tử giữa; nếu không thì sẽ tìm ở trong mảng con nằm ở bên trái phần tử giữa. Tiến trình sẽ tiếp tục như vậy trên mảng con cho tới khi tìm hết mọi phần tử trên mảng con này.

static int binarySearch(int[] list, int key) {
    int low = 0;
    int high = list.length - 1;
    while (high >= low) {
        int mid = (low + high) / 2;
        if (key < list[mid])
            high = mid - 1;
        else if (key == list[mid])
            return mid;
        else
            low = mid + 1;
    }
    return -1; /* Now high < low, key not found */
 }

Bước 3: Cài đặt phương thức main để thực thi ứng dụng.

public static void main(String[] args) {     

    System.out.println(binarySearch(list, 2));  /* 0 */ 
    System.out.println(binarySearch(list, 11)); /* 4 */     
    System.out.println(binarySearch(list, 79)); /*12 */  
    System.out.println(binarySearch(list, 1));  /*-1 */     
    System.out.println(binarySearch(list, 5));  /*-1 */ 
    System.out.println(binarySearch(list, 80)); /*-1 */

}

Bước 4: Chạy chương trình. Quan sát kết quả trả về.