Thuật toán Binary Search và cài đặt trong JavaScript

Binary Search (tìm kiếm nhị phân) là một thuật toán tìm kiếm hiệu quả trong một mảng đã được sắp xếp. Thuật toán này hoạt động bằng cách liên tục chia đôi mảng và so sánh phần tử cần tìm với phần tử ở giữa mảng, sau đó quyết định tìm kiếm tiếp tục ở nửa trên hay nửa dưới của mảng.

Cách hoạt động của Binary Search

1. Bắt đầu với hai chỉ số: left (bắt đầu của mảng) và right (kết thúc của mảng).
2. Tính chỉ số mid (giữa mảng).
3. So sánh phần tử tại chỉ số mid với phần tử cần tìm (target):
   • Nếu phần tử ở giữa bằng target, trả về chỉ số mid.
   • Nếu phần tử ở giữa lớn hơn target, cập nhật right thành mid - 1 để tìm kiếm trong nửa dưới.
   • Nếu phần tử ở giữa nhỏ hơn target, cập nhật left thành mid + 1 để tìm kiếm trong nửa trên.
4. Lặp lại các bước trên cho đến khi left lớn hơn right. Nếu không tìm thấy target, trả về -1.

Cài đặt Binary Search trong JavaScript

Dưới đây là mã nguồn chi tiết của thuật toán Binary Search trong JavaScript:

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

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

        if (arr[mid] === target) {
            return mid; // Trả về chỉ số của phần tử tìm thấy
        } else if (arr[mid] < target) {
            left = mid + 1; // Tìm kiếm trong nửa trên
        } else {
            right = mid - 1; // Tìm kiếm trong nửa dưới
        }
    }

    return -1; // Nếu không tìm thấy, trả về -1
}

// Ví dụ sử dụng:
let array = [2, 3, 4, 10, 40];
let target = 10;
let index = binarySearch(array, target);

if (index !== -1) {
    console.log(`Phần tử ${target} được tìm thấy ở chỉ số ${index}`);
} else {
    console.log(`Phần tử ${target} không có trong mảng`);
}

Giải thích mã nguồn

1. Hàm binarySearch:

   • Hàm nhận hai tham số: arr (mảng đã sắp xếp) và target (giá trị cần tìm).
   • Khởi tạo hai biến left và right để đánh dấu đầu và cuối mảng.

2. Vòng lặp while:

   • while (left <= right):
     • Tiếp tục lặp lại quá trình tìm kiếm miễn là left nhỏ hơn hoặc bằng right.

3. Tính toán chỉ số giữa:

   • let mid = Math.floor((left + right) / 2):
     • Tính toán chỉ số giữa của mảng bằng cách lấy trung bình của left và right.

4. So sánh phần tử giữa với target:

   • if (arr[mid] === target):
     • Nếu phần tử tại mid bằng target, trả về mid.
   • else if (arr[mid] < target):
     • Nếu phần tử tại mid nhỏ hơn target, cập nhật left thành mid + 1 để tìm kiếm trong nửa trên.
   • else:
     • Nếu phần tử tại mid lớn hơn target, cập nhật right thành mid - 1 để tìm kiếm trong nửa dưới.

5. Trả về kết quả nếu không tìm thấy:

   • Nếu vòng lặp kết thúc mà không tìm thấy target, hàm trả về -1 để chỉ ra rằng phần tử cần tìm không có trong mảng.

Thời gian và không gian của thuật toán

1. Thời gian:

   • O(log n) trong mọi trường hợp (tốt nhất, trung bình và xấu nhất) vì mỗi lần lặp giảm kích thước của mảng cần tìm kiếm đi một nửa.

2. Không gian:

   • O(1) vì thuật toán chỉ sử dụng một số biến phụ trợ và không yêu cầu thêm bộ nhớ ngoài mảng đầu vào.

Ưu và nhược điểm của Binary Search

Ưu điểm:

• Hiệu quả hơn Linear Search, đặc biệt với các mảng lớn.
• Thời gian thực thi O(log n) đảm bảo hiệu suất cao.

Nhược điểm:

• Chỉ hoạt động trên các mảng đã được sắp xếp.
• Cần thêm bước sắp xếp nếu mảng chưa được sắp xếp trước khi áp dụng Binary Search.

Binary Search là một thuật toán tìm kiếm mạnh mẽ và hiệu quả khi làm việc với các mảng đã được sắp xếp. Nó giúp giảm đáng kể số lượng so sánh cần thiết để tìm một phần tử so với Linear Search.