Tìm kiếm nhị phân (Sử dụng đệ quy)

Giới thiệu

Tìm kiếm nhị phân (Binary Search) hay còn gọi là tìm kiếm nửa khoảng (half-interval search), tìm kiếm logarit (logarithmic search), hay binary chop, là một thuật toán tìm kiếm xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp. Thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng. Nếu hai giá trị không bằng nhau, phần nửa mảng không chứa giá trị cần tìm sẽ bị bỏ qua và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa và so sánh với giá trị cần tìm, cứ thế lặp lại cho đến khi tìm thấy giá trị đó. Nếu phép tìm kiếm kết thúc khi nửa còn lại trống thì giá trị cần tìm không có trong mảng.

Ý tưởng

Tìm kiếm nhị phân chỉ có thể cài đặt trong một mảng đã được sắp xếp. Nếu mảng đó chưa được sắp xếp, hãy sắp xếp nó trước trước khi cài đặt thuật toán.

Có 2 cách để cài đặt thuật toán Tìm kiếm nhị phân:

1. Sử dụng vòng lặp
2. Sử dụng đệ quy

Trong bài viết này, mình sẽ hướng dẫn các bạn sử dụng đệ quy để cài đặt thuật toán. Phương pháp đệ quy này tuân theo nguyên tắc “chia để trị” gồm những bước như sau:

Bước 1: Khởi tạo mảng và sắp xếp các phần tử trong mảng (theo thứ tự bé đến lớn) và mình chọn phần tử x = 4 là phần tử cần được tìm kiếm.

Bước 2: Đặt 2 con trỏ low và high ở vị trí đầu và cuối của mảng tương ứng với phần tử nhỏ nhất và phần tử lớn nhất của mảng.

Bước 3: Tìm phần tử ở giữa mảng mid = (low + high) / 2.

Bước 4: Nếu x = arr[mid] thì trả về mid, nếu không ta tiếp tục so sánh.

Bước 5: Nếu x > arr[mid], so sánh x với các phần tử ở phía bên phải của mid bằng cách thay low = mid + 1.

Bước 6: Nếu x < arr[mid], so sánh x với các phần tử ở phía bên trái của mid bằng cách thay high = mid – 1.

Bước 7: Lặp lại từ bước 3 đến bước 6 cho đến khi con trỏ low gặp high.

Bước 8: Và cuối cùng phần tử x = 4 đã được tìm thấy.

Cài đặt

class BinarySearch {
  int binarySearch(int array[], int x, int low, int high) {

    if (high >= low) {
      int mid = low + (high - low) / 2;

      // If found at mid, then return it
      if (array[mid] == x)
        return mid;

      // Search the left half
      if (array[mid] > x)
        return binarySearch(array, x, low, mid - 1);

      // Search the right half
      return binarySearch(array, x, mid + 1, high);
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("Not found");
    else
      System.out.println("Element found at index " + result);
  }
}

Đánh giá thuật toán

Độ phức tạp thuật toán:

• Trường hợp tốt: O(1)
• Trung bình: O(log(n))
• Trường hợp xấu: O(log(n))

Không gian bộ nhớ sử dụng: O(n)

Cách sử dụng:

• Là thuật toán tìm kiếm phổ biến nhất hiện nay, 99% được áp dụng trong thiết kế 3D, đồ hoạ, ứng dụng,…
• Được ứng dụng vào thư viện của nhiều ngôn ngữ như Java, .NET, C++ STL,…
• Khi debugging, thuật toán tìm kiếm nhị phân được sử dụng để tìm ra chính xác vị trí gây lỗi.