Tìm Kiếm Nhị Phân: Dễ Hiểu và Thực Hành Đơn Giản

Mục Lục

1. Giới thiệu
2. Ý Tưởng Chính
3. Giải Pháp Cổ Điển
4. Trường Hợp Cạnh Tranh
5. Khoảng Đóng và Khoảng Mở
6. Lỗi Tràn
7. Mẹo và Thực Hành Tốt
8. Câu Hỏi Thường Gặp

1. Giới thiệu

Tìm kiếm nhị phân là một thuật toán quan trọng trong lập trình, giúp tìm kiếm một giá trị trong mảng đã được sắp xếp. Thay vì phải duyệt qua từng phần tử, thuật toán này chia đôi mảng để xác định vị trí của giá trị cần tìm, giúp tiết kiệm thời gian và tài nguyên.

Chúng ta sẽ sử dụng một mảng cụ thể trong ví dụ sau:

const arr = [2, 7, 8, 11, 15, 29, 31];
const target = 30;

2. Ý Tưởng Chính

2.1. Cách Hoạt Động

Tìm kiếm nhị phân hoạt động theo các bước sau:

1. Khởi tạo chỉ số: Đặt chỉ số trái (left) và phải (right) cho mảng.
   javascript Copy

   let left = 0;
   let right = arr.length - 1;

2. Tính chỉ số giữa: Tính chỉ số giữa (mid).
   javascript Copy

   const mid = Math.floor((left + right) / 2);

3. So sánh: So sánh giá trị tại chỉ số giữa với giá trị cần tìm (target).
   • Nếu bằng nhau, trả về chỉ số giữa.
   • Nếu target lớn hơn, cập nhật chỉ số trái.
   • Nếu target nhỏ hơn, cập nhật chỉ số phải.
4. Lặp lại: Tiếp tục lặp lại quá trình cho đến khi tìm thấy giá trị hoặc không còn phần tử nào để kiểm tra.

2.2. Ví Dụ Thực Tế

Giả sử chúng ta đang tìm kiếm giá trị 30 trong mảng đã cho:

• Bước 1: left = 0, right = 6
• Bước 2: Tính mid = 3, giá trị arr[mid] = 11
• Bước 3: Vì 30 > 11, cập nhật left = 4
• Tiếp tục lặp lại cho đến khi tìm thấy giá trị hoặc kết thúc.

3. Giải Pháp Cổ Điển

Dưới đây là một cài đặt điển hình cho thuật toán tìm kiếm nhị phân:

export function binarySearchClosedInterval(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

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

3.1. Phân Tích

Giải pháp này rất dễ hiểu và được sử dụng rộng rãi trong các bài viết và hướng dẫn. Nó giúp người mới làm quen với tìm kiếm nhị phân hiểu được cách hoạt động của thuật toán mà không cần ghi nhớ quá nhiều chi tiết.

4. Trường Hợp Cạnh Tranh

Một trong những lỗi phổ biến khi cài đặt tìm kiếm nhị phân là không xử lý đúng trường hợp khi chỉ số trái và phải gần nhau. Điều này có thể dẫn đến vòng lặp vô hạn. Ví dụ:

} else if (target < arr[mid]) {
  right = mid;
} else {
  left = mid;
}

Nếu không thực hiện các thay đổi cần thiết, thuật toán có thể không bao giờ kết thúc.

4.1. Giải Pháp

Đảm bảo cập nhật chỉ số right hoặc left theo cách sau:

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

5. Khoảng Đóng và Khoảng Mở

5.1. Khoảng Đóng

Khoảng đóng (closed interval) bao gồm cả hai đầu mút:

for (let i = 0; i <= arr.length - 1; i++) {}

5.2. Khoảng Mở

Khoảng mở (half-open interval) chỉ bao gồm đầu mút bên trái:

for (let i = 0; i < arr.length; i++) {}

5.3. Tìm Kiếm Nhị Phân Với Khoảng Mở

Dưới đây là cách cài đặt tìm kiếm nhị phân sử dụng khoảng mở:

function binarySearchHalfOpenInterval(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

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

  return (left < arr.length && arr[left] === target) ? left : -1;
}

6. Lỗi Tràn

Khi tính toán chỉ số giữa có thể xảy ra lỗi tràn trong các ngôn ngữ lập trình với kiểu số nguyên cố định. Để tránh điều này, sử dụng công thức an toàn hơn:

const mid = left + Math.floor((right - left) / 2);

7. Mẹo và Thực Hành Tốt

• Kiểm tra đầu vào: Luôn kiểm tra các trường hợp đặc biệt như mảng rỗng hoặc giá trị không tồn tại.
• Tối ưu hóa: Cố gắng tối ưu hóa mã nguồn để giảm thiểu thời gian thực thi và bộ nhớ sử dụng.
• Tài liệu: Ghi chú lại mã để người khác có thể hiểu được logic của bạn.

8. Câu Hỏi Thường Gặp

Tìm kiếm nhị phân có thể áp dụng cho mảng không sắp xếp không?

Không. Tìm kiếm nhị phân chỉ hoạt động với mảng đã được sắp xếp.

Có cách nào nhanh hơn không?

Tìm kiếm nhị phân là một trong những cách nhanh nhất cho tìm kiếm trong mảng đã sắp xếp, với độ phức tạp O(log n).

Hy vọng bài viết này giúp bạn hiểu rõ hơn về thuật toán tìm kiếm nhị phân và cách áp dụng nó trong lập trình. Hãy thử nghiệm và thực hành để thành thạo hơn!