Binary Search (Tìm kiếm nhị phân)

Posted on by mtoplistChuyên mục:Top List

Binary Search (Tìm kiếm nhị phân) được áp dụng cho mảng hoặc danh sách đã được sắp xếp, với kích thước tập dữ liệu lớn. Nó là một thuật toán tìm kiếm rất nhanh, vì độ phức tạp tính toán của nó chỉ là O(log n).

1. Cơ chế hoạt động của Binary Search

Điều kiện tiên quyết để sử dụng Binary Search là mảng hoặc danh sách phải được sắp xếp trước.

Về cơ bản thuật toán này sẽ loại bỏ được một nửa số phần tử sau mỗi bước so sánh. Giả sử x là phần tử cần tìm kiếm:

  • So sánh x với phần tử ở giữa.
  • Nếu x khớp với phần tử ở giữa, ta trả về chỉ số của phần tử ở giữa đó.
  • Nếu x lớn hơn phần tử ở giữa, chắc chắn x nằm ở một nửa danh sách phía bên phải của phần tử ở giữa. Và ta tiếp tục tìm kiếm x ở nửa danh sách đó đến khi tìm thấy hoặc không.
  • Ngược lại, ta tìm kiếm x ở nửa danh sách phía bên trái phần tử ở giữa.

Lấy ví dụ một mảng đã được sắp xếp với các giá trị {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}. Hình ảnh dưới đây sẽ mô tả tìm kiếm vị trí của phần tử có giá trị là 23 ở trong mảng bằng Binary Search:

Image Source: GeeksforGeeks

2. Cài đặt Binary Search

Có 2 phương pháp cài đặt thuật toán Binary Search:

  • Phương pháp Đệ quy
  • Phương pháp Vòng lặp

2.1. Phương pháp Đệ quy

BinarySearchRecursive

package com.icancodeit.algorithm.searching.binary;

public class BinarySearchRecursive {

  public static int binarySearch(int[] arr, int left, int right, int target) {
    if (right >= left) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == target) {
        return mid;
      }

      if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target);
      }
      return binarySearch(arr, mid + 1, right, target);
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int result = binarySearch(arr, 0, arr.length - 1, 23);
    if (result == -1) {
      System.out.println("Element not found in array.");
    } else {
      System.out.println("Element found at index = " + result);
    }
  }

}

Kết quả

Element found at index = 5

2.2. Phương pháp vòng lặp

BinarySearchIterative

package com.icancodeit.algorithm.searching.binary;

public class BinarySearchIterative {

  public static int binarySearch(int[] arr, int left, int right, int target) {
    while (right >= left) {
      int mid = left + (right - left) / 2;
      if (arr[mid] == target) {
        return mid;
      }

      if (arr[mid] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int result = binarySearch(arr, 0, arr.length - 1, 23);
    if (result == -1) {
      System.out.println("Element not found in array.");
    } else {
      System.out.println("Element found at index = " + result);
    }
  }
}

Kết quả

Element found at index = 5

3. Phân tích độ phức tạp của Binary Search

  • Time Complexity: O(log n)

Đọc thêm:

https://www.studytonight.com/data-structures/binary-search-algorithm

https://www.geeksforgeeks.org/binary-search/

Advertisement

mtoplist